The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 votes

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

asked in Theory of Computation by Veteran (52.1k points) | 1.7k views

4 Answers

+20 votes
Best answer

$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.

Answer is option B.

answered by Boss (30.5k points)
edited by
+14 votes

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.

SO answer :-


answered by Boss (41k points)
How to find DCFL and CFL ? can you please explain the difference between these two and how to identify them ?

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. 

+5 votes
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
answered by Veteran (61.5k points)
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
+2 votes
The answer is B.
answered by Boss (19.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,811 questions
54,540 answers
75,603 users