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

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