Language and Acceptability

1. Languages Accepted by Turing Machine ==(Type 0)==

These are called Recursively Enumerable (RE) languages.

Definition: A Turing Machine (TM) accepts all languages that are computably enumerable, i.e.,

There exists a TM that will accept any string in the language
It may or may not halt for strings not in the language

Key Characteristics:

Grammar: Unrestricted Grammar
Rules: Productions of the form α → β, where α, β ∈ (V ∪ T)* and α ≠ ε
Most powerful class of languages
Includes all Type 1, 2, 3 languages
Turing Machines can simulate any computation

Not Accepted: Turing Machines do not accept:

Non-computable languages, i.e., languages for which no TM exists at all
Undecidable languages can’t be fully solved (TM might not halt), but they are still RE

Examples of Turing-Acceptable Languages:

L = { a^n b^n c^n | n ≥ 1 }
L = { ww | w ∈ {a, b}* }
L = { palindromes over {a, b} }
L = { M | M is a valid C++ program that prints "yes" }
L = { ⟨M, w⟩ | Turing machine M accepts input w }
Any language that requires multiple stacks or tapes
Any language describing complex patterns, e.g., nested loops, programming logic
Any language accepted by:
- Finite Automata (Type 3)
- Pushdown Automata (Type 2)
- Linear Bounded Automata (Type 1)

Examples of Not Turing-Acceptable Languages:

L = { ⟨M⟩ | M does not halt on input ⟨M⟩ } → Diagonalization language (non-RE)

Conclusion:

Turing Machines accept the broadest class of languages, including all formal languages you can describe by any algorithm.

2. Languages Accepted by Linear Bounded Automata (Type 1 / CSG)

These are called Context-Sensitive Languages (CSLs).

Definition: A Context-Sensitive Grammar (CSG) accepts languages where:

Production rules are of the form: αAβ → αγβ, where |γ| ≥ 1
Length of the string does not decrease in any derivation step
Grammar is non-contracting (except S → ε if ε is in the language)

Key Characteristics:

Grammar: Context-Sensitive Grammar
Machine: Linear Bounded Automaton (LBA)
Memory: Finite tape bounded by input size
More powerful than PDA, but less powerful than TM
Can handle multiple dependencies
Includes all regular and context-free languages

Not Accepted by CSG:

Context-sensitive grammars cannot accept:
- Languages that are not recursively enumerable
- Languages requiring unbounded non-linear memory
- Languages with undecidable or non-computable structure

Examples of CSG-Acceptable Languages: ✅

L = { a^n b^n c^n | n ≥ 1 }
L = { a^n b^m c^n | n, m ≥ 1 }
L = { a^n b^n a^n | n ≥ 1 }
L = { ww | w ∈ {a, b}* }
L = { strings with equal number of a, b, and c in any order }
L = { an bn cn dm | n, m ≥ 1 }
Any language where length and symbol position must be preserved
All languages of Type 2 (CFL) and Type 3 (RL)

Examples of Not CSG-Acceptable Languages: ❌

L = { ⟨M⟩ | M does not halt on input ⟨M⟩ } → Halting Problem (non-RE)
L = { w | w is a valid C++ program that prints "yes" }
L = { M | M is a TM that accepts empty string }
Any language requiring general Turing-complete logic with unbounded memory

Conclusion:

Context-Sensitive Grammars accept all languages that need bounded, but context-aware structure
They include all regular and context-free languages
Cannot simulate Turing Machines, hence cannot accept non-RE or undecidable languages

3. Languages Accepted by Pushdown Automata (Type 2 / CFG)

These are called Context-Free Languages (CFLs).

Definition: A Context-Free Grammar (CFG) accepts languages where:

Production rules are of the form: A → α, where A ∈ V (non-terminal), α ∈ (V ∪ T)*
Only one non-terminal on LHS, and no context is required

Key Characteristics:

Grammar: Context-Free Grammar
Machine: Pushdown Automaton (PDA)
Memory: Uses 1 stack (can match nested structures)
All regular languages are also context-free
Can’t match multiple dependencies like a^n b^n c^n

Not Accepted by CFG:

CFGs do not accept languages that require:
- More than one dependency check
- Equal count matching across more than two symbols
- Copying/mirroring of substrings
- Non-linear memory (can’t simulate two stacks)

Examples of CFG-Acceptable Languages: ✅

L = { a^n b^n | n ≥ 0 }
L = { 0^n 1^n | n ≥ 0 }
L = { a^n b^m | n, m ≥ 0 }
L = { w ∈ {a, b}* | w is a palindrome } ⭐
L = { (ⁿ)^n | balanced parentheses } ⭐
L = { w | number of a's = number of b's, and all a's come before b's }
L = { a^n b^n + c^m | n, m ≥ 0 }
Any language described by recursive or nested patterns using a single stack

Examples of Not CFG-Acceptable Languages: ❌

L = { a^n b^n c^n | n ≥ 1 } ⭐
L = { ww | w ∈ {a, b}* } ⭐
L = { a^n b^n a^n | n ≥ 1 }
L = { ⟨M, w⟩ | Turing machine M accepts input w }
L = { strings with equal number of a, b, and c in any order }
L = { a^n b^m c^n | n, m ≥ 0 }

Conclusion:

Context-Free Grammars accept all languages that can be parsed using a single stack
They include all regular languages (Type 3)
Cannot handle multiple parallel dependencies or simulate Turing machines

4. Languages Accepted by Finite Automata (Type 3 / Regular Grammar)

These are called Regular Languages (RLs). Definition: A Regular Grammar (RG) accepts languages where:

Production rules are of the form:
- Right-linear: A → aB | a
- Left-linear: A → Ba | a
No memory or stack is used
Grammar is contracting (produces shorter or same-length strings)

Key Characteristics:

Grammar: Regular Grammar (Left or Right Linear)
Machine: Finite Automaton (FA / DFA / NFA)
Memory: No memory (finite states only)
Least powerful in Chomsky hierarchy
Cannot count or track nested structures
Suitable for simple pattern-based languages

Not Accepted by RG:

Regular grammars cannot accept:
- Languages that need counting/matching
- Nested or recursive structures
- Languages requiring memory or stack

Examples of RG-Acceptable Languages: ✅

L = { a^n | n ≥ 0 }
L = { a^n b^m | n, m ≥ 0 }
L = { strings ending with 'ab' }
L = { strings with no two consecutive b's }
L = { w ∈ {0,1}* | w contains even number of 0s }
L = { a^n b^n | n = 0 or 1 }
L = { w | w does not contain substring 'aa' }
L = { binary strings divisible by 3 }
Any language defined by a regular expression

Examples of RG-Acceptable Languages: ❌

L = { a^n b^n | n ≥ 1 } → needs counting
L = { ww | w ∈ {a, b}* } → needs memory
L = { a^n b^n c^n | n ≥ 1 } → not regular
L = { w | w is a palindrome }
L = { a^p | p is prime } → non-regular
L = { w | number of a's = number of b's }

Conclusion:

Regular Grammars accept languages with simple linear structure
They are the fastest and simplest to evaluate
They cannot handle counting, nesting, or memory-based constraints
Subset of CFLs and CSLs