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

Question

The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is
A)not recurcise
B)is recursive and deterministic CFL
C)is a regular language
D)is not a deterministic CFL but a CFL

Quizplus · Accepted Answer

The language L = { 0^i 2 1^i | i ≥ 0 } is a deterministic context-free language (CFL) because it can be recognized by a deterministic pushdown automaton (PDA). The PDA can push a symbol onto the stack for each 0 it reads, and then for each 1 it reads, it can pop a symbol off the stack, ensuring that the number of 0s and 1s are equal. The presence of the 2 in the middle serves as a deterministic point to switch from pushing to popping, which makes the language deterministic.

The Language L = { 0^i 2 1 ^I I>-0