GATE CS 2005 Q57 — Context-free Grammars and Push-down Automata

Let's analyze each language individually:

• $L_1 = \{ww^R \mid w \in \{0, 1\}^*\}$: This is the language of even-length palindromes. Because there is no marker to indicate the boundary between $w$ and $w^R$, a pushdown automaton (PDA) must non-deterministically guess the midpoint to start popping from the stack. Therefore, $L_1$ is a Context-Free Language (CFL) but not a Deterministic CFL (DCFL).
• $L_2 = \{w\#w^R \mid w \in \{0, 1\}^*\}$: The presence of the special marker $\#$ clearly separates $w$ from $w^R$. A Deterministic PDA (DPDA) can push the symbols of $w$ onto the stack, transition on reading $\#$ without changing the stack, and then match the remaining input with the popped symbols of the stack. Since it can be recognized by a DPDA, $L_2$ is a Deterministic CFL (DCFL).
• $L_3 = \{ww \mid w \in \{0, 1\}^*\}$: This is the copy language. To recognize $L_3$, we need to match the first half of the string with the second half in the exact same order (FIFO). Since a PDA uses a LIFO stack, it cannot recognize this language. Using the pumping lemma, it can be proven that $L_3$ is not a CFL at all.

Comparing these findings with the options:

• Option A is false because $L_1$ is non-deterministic.
• Option B is true because $L_2$ is a DCFL.
• Options C and D are false because $L_3$ is not a CFL.