edited by
20,984 views
50 votes
50 votes

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
edited by

9 Answers

Best answer
46 votes
46 votes
$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$
edited by
34 votes
34 votes

B is correct as confirmed by Shai Simonson Sir.

26 votes
26 votes

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

$III$ and $IV$ is CSL.

B is answer.

edited by
14 votes
14 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
Answer:

Related questions

40 votes
40 votes
1 answer
3