The Gateway to Computer Science Excellence

+22 votes

Consider the following languages:

- $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$
- $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$
- $\{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0 \}$
- $\{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?

- I and IV only
- I and II only
- II and III only
- II and IV only

+5

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

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

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,z_{0}/bz_{0} ), means if the input symbol is b and top of the stack is z_{0} (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.

+2

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

+2

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.

+24 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$

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$

+3

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

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

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

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

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

+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 :)

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 :)

+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

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

+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**

+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)**

+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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,651 questions

56,214 answers

194,173 comments

95,428 users