Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2007
Hard
The language L = {0ⁱ 2 1ⁱ | i ≥ 0} over the alphabet {0,1,2} is
- Anot recursive
- recursive and is a deterministic CFL
- Ca regular language
- Dnot a deterministic CFL but a CFL
Explanation
This language needs counting (matching the number of 0s and 1s around a single '2' marker), so it's not regular. But it IS context-free and can be recognized by a deterministic PDA: push each 0, then on seeing '2' switch modes, and pop one symbol per '1', accepting exactly when the stack empties precisely at end of input. Since it has a DPDA, it's a deterministic CFL, and all CFLs (deterministic or not) are recursive (decidable).
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.