GATE CS 2007 Q30 — Regular and Context-free Languages

To determine the class of the language $L = \{0^i 2 1^i \mid i \geq 0\}$ over the alphabet $\{0, 1, 2\}$, let us analyze its properties:

1. Not Regular: The language requires matching the number of $0$s before the marker $2$ with the number of $1$s after the marker $2$. Since a finite automaton has finite memory, it cannot keep track of an arbitrary count $i$. Thus, $L$ is not a regular language (eliminating Option C).
2. Deterministic Context-Free Language (DCFL): We can construct a Deterministic Pushdown Automaton (DPDA) to accept $L$:
   • For every $0$ read from the input, push it onto the stack.
   • When the marker $2$ is encountered, transition to a new state without changing the stack. The marker $2$ uniquely determines when to stop pushing and start popping.
   • For every $1$ read, pop a $0$ from the stack.
   • If the input ends precisely when the stack becomes empty (except for the initial stack symbol $Z_0$), accept the string.
   Since there is no non-determinism involved at any step, $L$ is a deterministic CFL (eliminating Option D).
3. Recursive: Every deterministic context-free language is also a context-free language, and all context-free languages are recursive (decidable). Thus, $L$ is recursive (eliminating Option A).

Therefore, the language $L$ is recursive and is a deterministic CFL.