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

Consider the following languages:

  1. $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$
  2. $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$
  3. $\{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0 \}$
  4. $\{a^mb^nc^pd^q \mid mn =p+q, \text{ where } m, n, p, q \geq 0 \}$

Which of the above languages are context-free?

  1. I and IV only
  2. I and II only
  3. II and III only
  4. II and IV only
in Theory of Computation by Boss (16.2k points)
edited by | 4.5k views
+2
Option (B) is the correct one
+4
m+p=n+q can we rewritten as (m-n=q-p OR n-m=p-q) this can be easily checked by making a NON DETERMINISTIC PUSH DOWN AUTOMATA hence CFL  and we know 2 is DCFL hence CFL :)
0
look at the proof below
0
where is the proof? i dont think what i commented above is wrong u can try constructing a NDPDA for 1 with what the hint i have given :)
0
I've answered why 4 is false and 2 is correct:)
0
B is correct
0
I've a doubt. for first option let string=$a^3b^4c^2d^1$

i push all 3 a's. then I pop one 'a' for every 'b'. now I'm left with 'b' and stack top is empty. what to do next? how is first option CFL?
+1

follow these transition:

Q(b,z0/bz0 ), means if the input symbol is b and top of the stack is z0 (or empty) then push b

once you start seeing  c then for every input c if b is at the top of the stack pop the b and once the stack is empty start pushing c , and once you start seeing d pop the c .

I hope you got it.

+4

Check this out for the first language:

0
bro you made two cases, that shows it is non deterministic
+1

@Vegeta Both cases are mutually exclusive, we can have either case 1 or 2 not both, so its deterministic.

0
yeah that's why you have to make PDA for both case, you dont know what input would be.
+1

Initially we push 'a' and pop 'b' for each 'a' in both cases and then we define multiple set of transitions in PDA to cover both cases. We can deterministically know which case is the right one by having information about top of the stack and next input symbol.

If #a >= #b: We push 'a' and then pop b for each 'a', ultimately we would exhaust all b's and there would still be some a's left in the stack. From this we know this is case #1, so we will have a sequence of transitions for this case.

If #a < #b: We push 'a' and then pop b for each 'a', at some point we will see there are still b's left while all a's are removed from stack (empty stack) then we know this is from case #2. So we will follow a different set of transitions from here.

Note: Both sets of transitions are defined in the diagram.

10 Answers

+23 votes
Best answer
$a)\ \{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$

Grammar :
$S \longrightarrow aSd\ |\ ABC\ |\in$
$A \longrightarrow aAb\ |\ ab\ |\in $
$B \longrightarrow bBc\ |\ bc\ |\in$
$C \longrightarrow cCd\ |\ cd\ |\in $

Above Grammar is CFG so it will generate CFL.


$b)\ \{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$

Grammar :
$S \longrightarrow AB\ |\in $
$A \longrightarrow aAb\ |\ ab$
$B \longrightarrow cBd\ |\ cd$

Above Grammar is CFG so it will generate CFL.


$c)\ \{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0 \}$
More than one comparison so NOT CFL.


$d)\ \{a^mb^nc^pd^q \mid mn =p+q, \text{ where } m, n, p, q \geq 0 \}$
It is CSL but NOT CFL.

Correct Answer: $B$
by Veteran (60k points)
edited by
0
bro...answer selected ??

which one is correct..i think its D
0
I have proved why 4 is false,see below.
0
Sir I think its 1 and 2
+1
@shivanisrivashini Yes, it is :)
0
Why is the fourth one csl?
+1
for 1 : m + p =n + q

can be written as m + p - n - q = 0  => m - n + p - q =0

push a

for each b  pop a ,

now if b's are more than a's push rest of a's

if a's are more than b's , a's will be there on stack.

for c's if a's are on stack push c's ,

for c's if b's are on stack pop b's

for d's if a's or c's are on stack pop 1 a or c for each d.

for d's if b's on stack (you can stop here itself as m - n + p - q  will not be zero)

 

for 4 : mn = p+q

what it means is "for each a push n b's on stack"

suppose if we pushed all a's on stack and now b start arriving ,suppose now first b arrived ,  at this stage we don't know how many b's will arrive eventually . hence we can't push exact number of b's corresponding to this first b's.

hence this is not CFL
0

@mehul vaidya could you pls tell example for 4 m not getting what mn means? 

0
mn simply means order of a multiplied by order of b. what is confucion in that?
0
i m not getting how to draw pda mn=p+q

suppose

m=3 n=2 p=4 q=4

here what mn ?Doubt how to draw pda for mn
0
m still not getting how the first option is CFL

suppose m=3 ,n=2 ,p=3 ,q=2

then .string would be : aaabbcccdd.   how to push or pop ?

if after PUSH(a) ,PUSH(b) is done , then pls someone explain it
0

@Digvijay Pandey i have a doubt here:

For option a--

In the first production S-->aSd|ABC|epsilon, 

What is the need of S-->aSd?? I think your other productions will generate the language right??

+22 votes

$I$ and $II$ is CFL since can be done via single stack.

$III$ and $IV$ is CSL.

B is answer.

by Veteran (62.3k points)
edited by
+1
Kindly explain how $I$ can be done via single stack.
+2
push on a and c , pop on b and d.

at the end stack is empty and hence cfl.

try  this eg: aabccddd
0
@gari what will happen for the input aabbbbccccdd?
+1
push 2 a's.

pop 2 a's for 2 b's  ( now stack is empty).

push 2 b's .

pop 2 b's for 2 c's.(now stack empty).

push 2 c's.

pop 2 c's for 2 d's ( stack empty , input empty ->accept)

note: think of (ac) in one team and (bd) in another team.

i am not able to get pda for this L. i'll post it when i'll get it :)
+17 votes

B is correct as confirmed by Shai Simonson Sir.

by (327 points)
+8 votes
B is correct and one of the easiest solution for I is CFL  as m+p=n+q can be written as m-n+p=q so we can easily construct PDA for I in following steps:-

1)push X for every a

2)pop X for every b

3)push X for every c

finally 4) pop X for every d and if atlast we get empty stack so yes it is valid language so definitely I is CFL So option B.thanks
by Active (1.3k points)
0
The string abbcccdd belongs to the language but it is not being accepted by the machine described by your method...Can you help me with this..
+7 votes
I and II are CFL
by Junior (575 points)
+3 votes

II is obviously CFL

for option IV as multiplication symbol is not given there we can consider it as concatenation

lets take example

a^30 b^5 c^200 d^105
now here m=30 n=5 p=200 q=105

mn=p+q is   305=305

now we can design pda as following

1)push 10 'a' for Each input 'a' in stack

2)push all b's in stack

now stack contains 305 a's and b's for above example

3)match all a and b in stack with input c and d

4)if stack is empty and input is null then accept otherwise reject

Hence OPTION D

by (171 points)
+4
Concatenation is defined for Languages (Sets of strings) and for Strings. There is no such thing as Concatenation of Decimal Numbers i.e. Powers.  Correct answer is B.
+3 votes

Many might have marked B,but one must be able to rigorously prove it:

Why is 4 false?

Here we must know what m is.Multiplication can only be performed if we know one of its operands.There is no bound on m, and since you cannot count till infinity(counting requires a distinct state for each increment) and you cannot have infinite states counting is not possible.This can be done with the help of LBA

Why is 2 true?

We'll decompose the problem into 2 parts as we don't have to be deterministic.

Case 1:

m-n = p-q .Do,simple push and pop for 'a' and 'b' respectively.Now,if 'b' is one the stack terminate . else do the similar operation for 'c' and 'd' .Now compare the leftover 'a' with leftover 'c',this is again trivial.

Case 2: n-m = p-q can be done similarly.

Answer:b)

by Junior (919 points)
edited by
0
Can I  justify the first as cfl as write m + p = n + q

It can also be written in the form of m - q = n - p

I can interpret it as push a and b then for every c pop b and for every d pop a untill the stack is empty .Therefore it can be called as cfl am I correct
0
How counting requires a distinct state for each increment?
+1 vote
For I to be cfl one more condition need to be satisfied along with m+p=n+q that is m>=n

Reference:

https://www.cs.utexas.edu/~cline/ear/automata/CS341-Fall-2004-Packet/3-SupplementaryMaterials/D-SuppContextFree.pdf

check page no 10 of pdf

for option IV as multiplication symbol is not given there we can consider it as concatenation

lets take example

a^30 b^5 c^200 d^105
now here m=30 n=5 p=200 q=105

mn=p+q is   305=305

now we can design pda as following

1)push 10 'a' for Each input 'a' in stack

2)push all b's in stack

now stack contains 305 a's and b's for above example

3)match all a and b in stack with input c and d

4)if stack is empty and input is null then accept otherwise reject
by (171 points)
edited by
0
Can I  justify the first as cfl as write m + p = n + q

It can also be written in the form of m - q = n - p

I can interpret it as push a and b then for every c pop b and for every d pop a untill the stack is empty .Therefore it can be called as cfl am I correct
+1 vote

Check this out for the first language:

by Active (2k points)
0 votes
I don't think the options are correct(The numbering is wrong). But I can definitely say that I and II, both are CFL as you easily construct PDAs for them. You can easily count the m's, n's & p's, q's in them and them push/pop accordingly.

III is definitely not a CFL. You cannot construct a PDA for it as you have to ensure that m = n = p, that means counting 3 of them and it is also given that p does not equal q, so q can be anything.

So I hope you can figure out the answer(The options are incorrect I think. So, check out!) :)
by (47 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,092 questions
55,319 answers
190,838 comments
86,198 users