851 views

The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is:

1. not recursive

2. is recursive and is a deterministic CFL

3. is a regular language

4. is not a deterministic CFL but a CFL

$L=\left\{0^i21^i \mid i \geq 0\right\}$ has only one comparison that can be done using a DPDA. Hence, its DCFL.

Context free languages are a proper subset of Recursive Languages. $\therefore$ it is recursive too.

selected

L = {0i21i |  i>=0 } is deterministic CFL,

Evert DCFL is recursive. As we have membership algorithm for DCFL (Or say CFL in general) , that's why it is recursive. In fact DCFL is subset of Recursive Languages.

B

push all 0  then skip 2 then for every 1 pop one 0 .. done by 1 stack without any confusion.. so dcfl.

dcfl⊆ cfl ⊆ csl ⊆ rec ⊆re
transition for skip ??? i am getting little bit confused there ....
yes when 2 will come we don't need to perform any operation, therefore, we will bypass (skip) 2 and then perform a pop operation on seeing 1