The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2.3k views

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
asked in Theory of Computation by Veteran (111k points)
edited by | 2.3k views

1 Answer

+30 votes
Best answer
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.
answered by Veteran (367k points)
edited by
0
For L3 and L4 --->for each 0, push two 0's on stack?
0

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 ?

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

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

S→0X

X→00X1 | ^

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

S AX|XB

X 00X1|^

A 0A|0

B 1B|1

+1
All are DCFL?
+2
Yes all are DCFL, we can design Deterministic PDA for all of them
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....

0
not closed, means it may or may not be .
+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?
+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"

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}

0

iarnav

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

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
Doubt

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

We can L3 can be accepted if there is one zero on to the stack??
0
we can also say that if i not = j i.e.....i=2j or j=2i
Answer:

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

44,019 questions
49,545 answers
162,696 comments
65,769 users