Consider the following languages over the alphabet ∑

Home » Theory of Computation » Theory of computation miscellaneous » Question

Consider the following languages over the alphabet
∑ = {0, 1, c}:
L₁ = {0ⁿ 1ⁿ | n ≥ 0}
L₂ = {wcw^r |w ∈ {0, 1}*}
L₃ = {ww^r |w ∈ {0, 1}*}
Here, w^r is the reverse of the string w. Which of these languages are deterministic Context-free languages?

1. None of the languages
2. Only L₁
3. Only L₁ and L₂
4. All the three languages

Correct Option: C

L1 and L2 have deterministic push down automata but for L3 only not-deterministic PDA is possible. So L3 is not deterministic.