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\}$

  1. Only $L2$ is context free.
  2. Only $L2$ and $L3$ are context free.
  3. Only $L1$ and $L2$ are context free.
  4. All are context free
in Theory of Computation by
edited by | 4.1k views

2 Answers

+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.
edited by
For L3 and L4 --->for each 0, push two 0's on stack?

Hi @Arjun sir , in case of L={01j  | 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 ?

No. That is wrong. Here the only condition to check is if i = j, the else case will be i <> j.

let i,j>=0
L2={0i1∣ i=j}  

S → 0S1 | ^
L1={0i1∣  j} either 0's are more , 0+0i1j or 1's are more 0i1j1+

S→ AX|XB ,

X→0X1|^ ,

A→0A|0  ,

B→ 1B|1 

L3={0i1∣ i=2j+1}

02j+11 that is 002j1j


X→00X1 | ^

L4={0i1∣ i2} either 0's are more 0+02j1j  or 1's are more 02j1j1+


X 00X1|^

A 0A|0

B 1B|1

All are DCFL?
Yes all are DCFL, we can design Deterministic PDA for all of them

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

not closed, means it may or may not be .
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?
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
here there is a mistake in the solution ,  the logic of pushing two  0 for each 0 is wrong for l3 and l4

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

Valid string in L3 = 0001 (when j=1, i=3) 

1st "0" ------ do nothing.

for 2nd and 3rd 0 i.e "00" push only one "0"  on stack.

for 1st and only "1" in string POP the "0" we pushed in above step.

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



explain first and fourth part using complement .how this will accept?

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.
@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?

If i>j in l1 then number of 0 remaining in the stack then it is accepted or not?
@pravin sir please answer this doubf

We can L3 can be accepted if there is one zero on to the stack??
we can also say that if i not = j i.e.....i=2j or j=2i
Awesome sir. Thank you.
Is not L1 regular (any number of 0's followed by any number of 1's). and hence CFL ??

@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 ???

Sir, In L3 you written do the same as L2, but it should be "do the same as L1 n?" Because when i=2j+1 stack will be non empty which is same as L1.

And same problem in L4, it should same same as L2 n ??
0 votes
All languages L1, L2, L3 and L4 has only one comparison and it can be accepted by PDA (single stack),
hence all are Context Free Languages.

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
52,315 questions
60,435 answers
95,248 users