Question

The language L = {0^i 21^i | i <= 0} over the alphabet {0,1,2} is
(A) not recursive
(B) is recursive and is a deterministic CFL
(C) us a regular language
(D) is not a deterministic CFI but a CFL

Answer 1

Answer on Question#38160 – Math - Other

(B) is recursive and is a deterministic CFL.

One can easily design a deterministic push down automata which scans the input left to right, when a 0 is encountered it stacks it, and moves to the right. When a 2 is encountered it switches from a stacking to a pop state and so long as a 1 comes in the input it pops a 0. When the input is exhausted and the stack is empty, it goes to a final state.