The Gateway to Computer Science Excellence
+33 votes
3.3k views

Let

$L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$,

$L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and

$L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\} $.  

Which of these languages are NOT context free? 

  1. $L_1$ only
  2. $L_3$ only
  3. $L_1$ and $L_2$
  4. $L_2$ and $L_3$
in Theory of Computation by Active (3.3k points)
edited by | 3.3k views
0
if we make a pda for the L3 it will accept strings have n+m=even numbers bur it won't be able to accpet the strings having  n+m=odd

cosider the string 000011110000 it can get accepted as we can make a ndpa for it. we can guess that we may have read  half of the string and make a transiion to the pop state of the ndpa but the same can't be done for strings of odd length.
ex-000111000
0

 Arjun sir , Praveen Saini sir pls see this is the reason given by me right ?

L1:     0n0m1n1m  accept by pda

for this we  push 0 ,then 0m and after that for 1m we pop 0m then for 1n we pop 0n

L2: 0n0m1n1m0m

DPDA possible for last 0 just paas

L3: 0n0m1n1m0n0m

for last 0n0m we cant make comparison 

+1
@set2018 for the second one, consider n=0 ... Then it's similar to the third.
0
Sir plz tell me L2 is not CFL

4 Answers

+42 votes
Best answer

Answer is (D)

$L_1$ is context-free. We count the number of $0$'s and check if the remaining number of $1$'s followed by 0's count to the initial number of $0$'s.

$L_2$ is not context-free. Here the number of $0$'s and the following $1$'s must be same, which can be checked using a PDA. But after that we must also ensure that the following number of $0$'s must be less than the previous count of $0$'s and $1$'s (otherwise $n < 0$, which violates the condition for acceptance) and we cannot do these two checks using a single PDA.

$L_3$ is again not context-free as it is nothing but equal number of $0$'s followed by equal number of $1$'s followed by equal number of $0$'s.

by Veteran (432k points)
edited by
0
@ARJUN SIR ,WHY L3 CANT BE CONTEXT FREE

WE CAN PUSH ALL 0'S TO THE STACK AND THEN SKIP ALL THE ONES THEN POP 0'S WITH INITIAL PUSHED 0'S
0
then how will we ensure #0 = #1?
0
AS PER MY ABOVE COMMENT WE CANT ENSURE #0=#1

BUT THE LANGUAGE IS ACCEPTED BY PDA.

1.PUSH ALL 0'S

2.SKIP IF ANY 1 COMES

3. POP 0'S WITH INITIAL

SINCE IT IS MENTIONED AS LANGUAGE AND THE LANGUAGE SHOULD BE "AS U MENTIONED IN THE ANS"

AND IS NOT ABLE TO ACCEPT .THAT'S WHAT THE REASION

AM I RT SIR?
+11

@asu $L_3$ is similar to $\{a^nb^nc^n \;|\;n\geq 0\}$

0
yes sir u r right...can't we draw pda for that ..and my above procedure for pda construction  is correct or not.

plz clarify this doubt sir
0

pda for L1 will also accept 0m+n1m0n , then How it can be context-free?

0
L1=0^n0^m1^m0^n ...we can do it with one stack
0
NO...
0
@arjun sir can u pls tell in detail how L1 is accpted using single stack and also how L2 is rejected by single stack ?

L
0
Cant L3 can be solve like this Push two 0's for every 0 ie 0^2n then pop 1 then pop all 0.
0
@rahul How will that ensure number of 0's at beginning equals number of 1's?

@Anjana For 1, Push 0 for every 0. Then when 1 comes start pop. Repeat the same for 0. If any other character comes go to a dead state. Accept on empty stack.
0

@Arjun Sir

0n+m1n+m0n+m0n 011n  00

Here for every  0n  we can push 02n   (1 zero to macth 0 and 1 zero to match 1 )

for every  0 we can push 02m , So ultimately for every 0 we are pushing 2 0's to the stack 

For all 1m  pop  0m   (0's will be on top of the stack)  ,for all 1n  pop   0n  (0's will be on top of the stack) 

We are still left with 0n+m on our stack, which can be matched to last 0n+m 

So isn't it CFL, What is wrong here Arjun Sir ?

+3
^Won't it accept 000011100000?
+1
Ok it should reject which is not there in the language also right!!

Got it.Thanx
0

@Arjun For L1 if we are pushing and popping the way you said then 0n+m1m0will also be accepted so it's not context free right?

+1

@Xylene  

See we don't know the value m and n it is just arbitary values,the ultimate idea is we need to push n+m 0's and pop 1's and 0's which should sum upto n+m

0
@arjun sir @praven sir

In L1, how can we ensure that #1's = no. of first 0's(i.e. no of occurences of first 0's) ?
0
@shu we dont have to, since $0^61^40^2$, $0^61^20^4$, $0^61^50^1$, $0^61^10^5$, etc are acceptable in $L_1$
+1
Someone please validate if my interpretation is correct for L1

We will push n+m zero's on to stack  then on seeing ones will pop zero's onee by one now as soon as 1's are over we keep on popping remaining zerosz with m zeros?
0

@Arjun

0n+m1n+m0n+m = 0n 0m 1m 1n  0n 0m 

Here for every  0n  we can push 02n   (1 zero to macth 0 and 1 zero to match 1 )

for every  0m  we can push 02m , So ultimately for every 0 we are pushing 2 0's to the stack 

For all 1m  pop  0m   (0's will be on top of the stack)  ,for all 1n  pop   0n  (0's will be on top of the stack) 

We are still left with 0n+m on our stack, which can be matched to last 0n+m 

So isn't it CFL, What is wrong here Arjun Sir ?

0

Then it will also accept the string 00100 which is INVALID string.

0
I understand why $L_1$ is a CFL but how do we reject strings of the form $0^{n + m}1^m0^n$ in our PDA construction? They are not part of the language.

If we push $n+m$ symbols on the stack and then pop them all out, we won't be able to distinguish between 1s and 0s during the pop phase.
+5 votes

Take language one by one:

  1. L1 is CFL Even DCFL since push all 1's , when first 0 come start pop untill stack is empty.Take language one by one:
  2. L3 is Non -CFL Even DCFL since push all 0's , when first 1 come start pop untill stack is empty, now at this point you forget what is the value of m+n since stack is empty So you need two stacks . if you took n+m=p then language look like 0^{p}1^{p}0^{p} .
  3. L2 is Non-CFL since  push all 0's , when first 1 come start pop untill stack is empty, now at this point you forget what is the value of m since stack is empty So you need two stacks .
by Veteran (63k points)
0
I get it.

Thanks, Bro!!
0

@Arjun sir and @Prashant. Sir In L2 is it possible All 0 push until 1st 1 comes then all 1 pop it till 0 come , once 0 come then next all 0 skip using this PDA possible or not???

 

0

@mesh90

It will accept those strings also which are not part of the language according to that logic. And if you are satisfied with $L_{3}$ then when you put n=0 in $L_{2}$ you will get $0^m1^m0^m$ which is same as $L_{3}$. Hence not CFL.

+2 votes

L2 and L3 are  like  language  a^nb^nc^n. which is csl . because there is two comparision so we cannot drow PDA .

by Boss (36.7k points)
0
What is wrong with my argument? Why is it invalid?
0 votes
for  the first one I can construct a grammar like this;
S->0S0|EPSILON|A
A->0A1|EPSILON
so this  is context free.

For the second one to construct it we need an npda with 2 stacks.
 Or we can argue like this that if n=0 then the resulting language becomes a^n b^n c^n which is not a cfg.

for the third one it is exactly like :
a^n b^n c^n which is not a CFG.
by Junior (811 points)
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
50,737 questions
57,398 answers
198,613 comments
105,456 users