Consider the following languages over the alphabet \(Σ = \{0,1,c\}\): \(L_1 =…
2014
Consider the following languages over the alphabet \(Σ = \{0,1,c\}\):
\(L_1 = \left\{0^n1^n\mid n \geq 0\right\}\)
\(L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}\)
\(L_3 = \left\{ww^r \mid w \in \{0,1\}^*\right\}\)
Here, \(w^r\) is the reverse of the string \(w\). Which of these languages are deterministic Context-free languages?
- A.
None of the languages
- B.
Only
\(L_1\) - C.
Only
\(L_1\)and\(L_2\) - D.
All the three languages
Attempted by 107 students.
Show answer & explanation
Correct answer: C
Answer: Only the languages L1 and L2 are deterministic context-free languages.
L1 = {0^n1^n}: A deterministic pushdown automaton can push each 0 onto the stack and, on reading the first 1, deterministically switch to popping and match every 1 with a 0. The switch is triggered by seeing a 1, so no nondeterminism is needed.
L2 = {w c w^r}: The central symbol c marks the midpoint of the string. A deterministic PDA can push symbols of w while reading the prefix, then upon reading c switch deterministically to popping and compare the remaining symbols with the stack. The presence of c removes the need to guess the midpoint.
L3 = {w w^r}: This language is context-free but not deterministic context-free. Without a separator marking the midpoint, a deterministic PDA cannot know when to stop pushing and start popping; it would have to guess the midpoint. That necessary guessing requires nondeterminism, so L3 is not a deterministic CFL.
Conclusion: Only L1 and L2 are deterministic context-free languages; L3 is CFL but not deterministic.
A video solution is available for this question — log in and enroll to watch it.