The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
1.9k 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$
asked in Theory of Computation by Active (3.7k points)
edited by | 1.9k 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.

1 Answer

+31 votes
Best answer
$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.
answered by Veteran (358k 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?
+8

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


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

40,770 questions
47,478 answers
145,652 comments
62,241 users