The Gateway to Computer Science Excellence

+27 votes

Consider the languages

$L1=\{0^i1^j\ \mid i \neq j\}, $

$L2=\{0^i1^j\mid i=j\},$

$L3=\{0^i1^j \mid i=2j+1\},$

$L4=\{0^i1^j \mid i\neq2j\}$

- Only $L2$ is context free.
- Only $L2$ and $L3$ are context free.
- Only $L1$ and $L2$ are context free.
- All are context free

+38 votes

Best answer

Correct Answer: $D.$ All are context free.

$L1 \rightarrow$ Push $0$ on stack and when $1$ comes, start popping. If stack becomes empty and $1$'s are remaining start pushing $1$. At end of string accept if stack is non- empty.

$L2 \rightarrow$ Do the same as for $L1$, but accept if stack is empty at end of string.

$L3 \rightarrow$ Do, the same as for $L2$, but for each $0$, push two $0$'s on stack and start the stack with a $0$.

$L4 \rightarrow$ Do the same as for $L1$, but for each $0$, push two $0$'s on stack

All are in fact DCFL. Pushing two $0$'s on stack might sound non-trivial but we can do this by pushing one symbol and going to a new state. Then on this new state on empty symbol, push one more symbol on stack and come back.

$L1 \rightarrow$ Push $0$ on stack and when $1$ comes, start popping. If stack becomes empty and $1$'s are remaining start pushing $1$. At end of string accept if stack is non- empty.

$L2 \rightarrow$ Do the same as for $L1$, but accept if stack is empty at end of string.

$L3 \rightarrow$ Do, the same as for $L2$, but for each $0$, push two $0$'s on stack and start the stack with a $0$.

$L4 \rightarrow$ Do the same as for $L1$, but for each $0$, push two $0$'s on stack

All are in fact DCFL. Pushing two $0$'s on stack might sound non-trivial but we can do this by pushing one symbol and going to a new state. Then on this new state on empty symbol, push one more symbol on stack and come back.

0

Hi @Arjun sir , in case of L_{1 }={0^{i }1^{j }| i<>j} , it can be either i>j or j>i , so it can not be DCFL . Am I correct ?

Same is the case with option D. Is this correct approach ?

+12

let i,j>=0
*L*2={0^{i}1^{j }∣ *i*=*j*}

S → 0S1 | ^
*L1*={0^{i}1^{j }∣ *i *≠ *j*} either 0's are more , 0^{+}0^{i}1^{j} or 1's are more 0^{i}1^{j}1^{+}

S→ AX|XB ,

X→0X1|^ ,

A→0A|0 ,

B→ 1B|1

*L*3={0^{i}1^{j }∣ *i*=2*j*+1}

0^{2j+1}1^{j }* that is *00^{2j}1^{j}

S→0X

X→00X1 | ^

*L*4={0^{i}1^{j }∣ *i*≠2*j *} either 0's are more 0^{+}0^{2j}1^{j }or 1's are more 0^{2j}1^{j}1^{+}

S →AX|XB

X→ 00X1|^

A→ 0A|0

B→ 1B|1

0

Hello, I have a doubt, as far I know, Complement of a CFL is not closed. If L = a^i b^j is $a^{i}b^{j}$ where i!=j , then its complement would be L (complement) a^{i}b^{j} where i == j. Hence the complement if not CFL.

Please correct me....

+2

For L3, pushing two 0's would have worked if j=2i+1, i.e if number of 1's were more than the number of 0's. But in this case number of 0's is more than the number of 1's.

e.g. 0000011 is a valid string for L3. How can this be processed by a PDA?

e.g. 0000011 is a valid string for L3. How can this be processed by a PDA?

+3

do nothing for first 0, then push one 0 one reading 2 0's ( one push ,one do thing) , then read one 1 pop one 0

+1

here there is a mistake in the solution , the logic of pushing two 0 for each 0 is wrong for l3 and l4

0

L3 = 1st "0" do nothing. then "**for every 2 0's push one 0 on stack" and for every "1" pop one "0"**

That's it, You'll reach end of string and stack has only stack alphabet, POP it and accept. {e,z0/e}

0

For L3, we can pop two 0s for one 1, and after all 1s are over, if the top has 0, pop it. If stack becomes empty, then accept, else reject.

0

@ARJUN sir, In the first case I think when they are saying i≠j, then there are two possibilities i<j or i>j but at a time only one will occur (because of OR), and we need only one stack to perform this action , when we come to make PDA then there will be 2 PDA's 1st be will i<j and second will be i>j. Thats why this is DCFL . if in a case i<j and i>j it will CSL because we need 2 stacks. Am I right sir?

0

@pravin sir please answer this doubf

We can L3 can be accepted if there is one zero on to the stack??

We can L3 can be accepted if there is one zero on to the stack??

0

@Arjun sir,

In the last one, i $\neq$ 2j means i = j or i = 3j or i = 4j or i = 5j or i = 6j or ..............i = nj

so, there are many no. of non-determinism, How this is DCFL ???

52,375 questions

60,615 answers

202,051 comments

95,433 users