Consider the following languages: I. \{a^{m} b^{n} c^{p} d^{q} ∣ m+p=n+q, where m, n, p, q \geq 0\} II. \{a^{m} b^{n} c^{p} d^{q} ∣ m=n and p=q, where m, n, p, q \geq 0\} III. \{a^{m} b^{n} c^{p} d^{q} ∣ m=n=p and p \neq q, where m, n, p, q \geq 0 IV. \{a^{m} b^{n} c^{p} d^{q} ∣ m n=p+q, where m, n, p, q \geq 0\} Which of the language above are context-free?

Correct Answer is : I and II only

GATE Computer Science (CS) 2018 Shift 1 Solved Paper

Question : 62 of 65

Marks: +1, -0

Consider the following languages:
I.

\;\; \{a^{m} b^{n} c^{p} d^{q} ∣ m+p=n+q

, where

m, n, p, q ≥ 0\}

II.

\{a^{m} b^{n} c^{p} d^{q} ∣ m=n

and

p=q

, where

m, n, p, q ≥ 0\}

III.

\{a^{m} b^{n} c^{p} d^{q} ∣ m=n=p

and

p ≠ q

, where

m, n, p, q ≥ 0

IV.

\{a^{m} b^{n} c^{p} d^{q} ∣ m n=p+q

, where

m, n, p, q ≥ 0\}

Which of the language above are context-free?

Solution:

\{a^{m} b^{n} c^{p} d^{q} ∣ m+p=n+q\}

is clearly CFL since, we can rearrange the equation as

m-n+p-q=0

which can be done by push, pop, and pop and check if stack is empty at end.
II.

\{a^{m} b^{n} c^{p} d^{q} ∣ m=n

and

p=q\}

is clearly CFL since, one comparison at a time can be done by pda.
III.

\{a^{m} b^{n} c^{ρ} d^{q} ∣ m=n=p

and

p ≠ q\}

is not CFL since

m=n=p

is a double comparison which cannot be done by PDA.
IV.

\{a^{m} b^{n} c^{p} d^{q} ∣ m n=p+q\}

is not a CFL, since

m n

involves multiplying number of a's and number b's which cannot be done by a PDA.
So, only I and II are CFL's.

Go to Question:

Prev Question

Next Question