1.4k 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.

edited

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

0
How to find DCFL and CFL ? can you please explain the difference between these two and how to identify them ?
+4

Identification of whether DCFL or CFL?

The very basic thing to look out first, is whether  you can generate that language using a PDA or not ? Relate it with stack and just by using push and pop can you generate it ? If so, its a CFL. Now if the PDA that you are using, is deterministic at each step, that is you are clear about the next move every single time, then it's a DCFL, otherwise if there is any non determinism  involved, that is there are some steps where more than one move is possible, and you are not certain about the action, then its CFL. While remembering the fact that DCFL is a proper subset of CFL.

Ex:  let L= {anbn}, it is CFL because, with the help of PDA (push down automata), we can recognize it. We have n a's followed by n b's. we can push all a and corresponding to each b, we can pop a. if they are equal stack will be empty. if a are more, stack will have a. if stack becomes empty before finishing string, it means we have more b. It is DCFL as well because, we know we have to push a and pop for b, the action is deterministic.

On the other hand, {wwR,  where w is a string of a and b} is non deteministic CFL because till half of the length, we have to push and then we have to pop. but we dont know length. So at each step, we will push the next symbol and pop the previous one to see which one works. so it is non deteminsitic. So a CFL will be either deterministic or non deterministic.

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
0
transition for skip ??? i am getting little bit confused there ....
0
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

1
2