GATE CS 2018 Q35 — Context-free Grammars and Push-down Automata

To determine which of the given languages are context-free, we analyze each one individually:

• Language I: $L_1 = \{a^mb^nc^pd^q \mid m+p=n+q\}$

  The condition can be rewritten as $m - n = q - p$. We can track this relation using a single stack (PDA):

  • Push for each $a$, pop for each $b$. If the stack becomes empty and more $b$'s arrive, push a placeholder for excess $b$'s.
  • Push for each $c$ (or pop if excess $b$'s are on the stack).
  • Pop for each $d$.

  Since a single stack is sufficient to verify the net difference, $L_1$ is context-free.

• Language II: $L_2 = \{a^mb^nc^pd^q \mid m=n \text{ and } p=q\}$

  This language can be written as the concatenation of two context-free languages:

  $$L_2 = \{a^m b^m \mid m \geq 0\} \cdot \{c^p d^p \mid p \geq 0\}$$

  Since context-free languages are closed under concatenation, $L_2$ is context-free.

• Language III: $L_3 = \{a^mb^nc^pd^q \mid m=n=p \text{ and } p \neq q\}$

  This requires matching three independent variables simultaneously ($m=n=p$), which is a classic non-context-free structure (similar to $\{a^n b^n c^n\}$). Thus, $L_3$ is not context-free.

• Language IV: $L_4 = \{a^mb^nc^pd^q \mid mn = p+q\}$

  The constraint involves multiplication of independent variables ($mn$), which cannot be tracked by a pushdown automaton. Thus, $L_4$ is not context-free.

Therefore, only languages I and II are context-free.