Consider the languages: L1 = {wwR |w ∈ {0, 1}*} L2 = {w#wR | w ∈ {0, 1}*},…
2005
Consider the languages:
L1 = {wwR |w ∈ {0, 1}*}
L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbol
L3 = {ww | w ∈ (0, 1}*)Which one of the following is TRUE?
- A.
L1 is a deterministic CFL
- B.
L2 is a deterministic CFL
- C.
L3 is a CFL, but not a deterministic CFL
- D.
L3 is a deterministic CFL
Attempted by 27 students.
Show answer & explanation
Correct answer: B
L1 is the language of palindromes over {0,1}, which is context-free but not deterministic; it requires a non-deterministic pushdown automaton. L2 uses the separator #, allowing a deterministic PDA to recognize it by pushing symbols until encountering # and then popping them in reverse order, making L2 a deterministic context-free language. L3 is the language of strings formed by repeating any string w twice, which is not context-free (can be proven using the pumping lemma). Therefore, only L2 is a deterministic CFL. The correct option reflects this analysis.
A video solution is available for this question — log in and enroll to watch it.