The language L = { 0ⁱ 2 1ⁱ | i ≥ 0 } over the alphabet {0,1,2} is
2007
The language L = { 0ⁱ 2 1ⁱ | i ≥ 0 } over the alphabet {0,1,2} is
- A.
not recursive
- B.
is recursive and is a deterministic CFL
- C.
is a regular language
- D.
is not a deterministic CFL but a CFL
Attempted by 35 students.
Show answer & explanation
Correct answer: B
The language L = { 0ⁱ 2 1ⁱ | i ≥ 0 } is recognized by a Deterministic Pushdown Automaton (DPDA). The DPDA pushes 0s onto the stack, reads the separator '2', and then pops one symbol for each subsequent 1.
Since it is a Deterministic Context-Free Language (DCFL), and all DCFLs are Recursive, the language is both recursive and a deterministic CFL.
A video solution is available for this question — log in and enroll to watch it.
Loading lesson…