GATE CSE 2018 | Question: 35

Question

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?

• A. I and IV only
• B. I and II only
• C. II and III only
• D. II and IV only

Comments

Option (B) is the correct one

---

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

---

look at the proof below

---

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

---

I've answered why 4 is false and 2 is correct:)

---

B is correct

---

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?

---

follow these transition:

Q(b,z₀/bz₀ ), means if the input symbol is b and top of the stack is z₀ (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.

---

Check this out for the first language:

---

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

---

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

---

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

---

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.

---

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

One of the grammars of above language was given in GATE1997-11.

---

For option (I), it can be written as m-n+p-q=0. This is easy to see as DCFL. Isn’t it?

---

@ rfzahid thanks this really clear my doubt. good work

 

Answer 1

$I)\ \{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.

$II)\ \{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.

$III)\ \{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.

$IV)\ \{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$

Comments

Abhrajyoti00

Actually $CSG$ can contain $\epsilon$ but either it must not be reachable from the initial state or it should be of the form   $S$ $→$ $aA$, $A$ $→$ $\epsilon$ (Assuming S as the initial state).

---

@Abhrajyoti00 @Kabir5454 @gatecse @Arjun sir

Language is generated with the help of Grammar, if the language containing ε, then why grammar is not containing??????

---

@mehul vaidya  I think there is a typo in line no 5 of your comment- if b's are more than a's push rest of a's( Push rest of b’s should be there.)

Answer 2

B is correct as confirmed by Shai Simonson Sir.

Comments

You are lucky to get in contact with him

---

unique stuff!

---

Bro is ready to knock on DONALD KNUTH's front door for a gate question. Excellent commitment.

Answer 3

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

$III$ and $IV$ is CSL.

B is answer.

Comments

@gari what will happen for the input aabbbbccccdd?

---

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

---

Nice. Thanks

Answer 4

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

Comments

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

---

This works only when (m-n) >=0

---

You’ve missed few condition checks, correct way to do this will be:

1. For a’s push a.
2. For b’s, pop a’s from the stack.
3. If there are extra b’s, and the stack is empty, push b’s.
4. For c’s, pop b’s (if exist in the top of the stack), else, push c’s.
5. For d’s, pop c’s.