GATE CS 2014 Set 3 Q36 — Context-free Grammars and Push-down Automata

A language is a Deterministic Context-Free Language (DCFL) if and only if it can be accepted by a Deterministic Pushdown Automaton (DPDA).

Let's analyze each language individually:

1. Language $L_1 = \{0^n 1^n \mid n \geq 0\}$:

   A DPDA can easily recognize this language. We push all incoming $0$s onto the stack. When the first $1$ is encountered, the automaton deterministically switches to a popping state, matching each subsequent $1$ with a $0$ from the stack. Since there is no ambiguity about when to start popping, $L_1$ is a DCFL.

2. Language $L_2 = \{w c w^r \mid w \in \{0,1\}^*\}$:

   The presence of the marker symbol '$c$' clearly demarcates the boundary between $w$ and its reverse $w^r$. A DPDA can push the characters of $w$ onto the stack, and upon reading '$c$', deterministically switch to matching the remaining input with the stack symbols. Because the transition point is deterministic, $L_2$ is a DCFL.

3. Language $L_3 = \{w w^r \mid w \in \{0,1\}^*\}$:

   Unlike $L_2$, there is no marker to indicate where $w$ ends and $w^r$ begins (for example, in the string $0110$, the split is not marked). A pushdown automaton must non-deterministically guess the midpoint to transition from pushing to popping. Thus, $L_3$ requires a Non-deterministic Pushdown Automaton (NPDA) and is not a DCFL (it is a CFL but not a DCFL).

Therefore, only $L_1$ and $L_2$ are deterministic Context-free languages.