GATE CS 2015 Set 3 Q32 — Context-free Grammars and Push-down Automata

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

1. Language $L_1 = \{a^m b^n a^n b^m \mid m, n \geq 1\}$

In $L_1$, the comparisons are nested (LIFO structure):

• The inner $b$'s are matched with the inner $a$'s ($b^n$ with $a^n$).
• The outer $a$'s are matched with the outer $b$'s ($a^m$ with $b^m$).

We can easily design a Pushdown Automaton (PDA) using a single stack: push $a$'s, push $b$'s, pop $b$'s for the next set of $a$'s, and then pop $a$'s for the final set of $b$'s.

Alternatively, we can write a Context-Free Grammar (CFG) for $L_1$:

Since a CFG exists, $L_1$ is context-free.

2. Language $L_2 = \{a^m b^n a^m b^n \mid m, n \geq 1\}$

In $L_2$, the comparisons are overlapping/cross-dependent (FIFO structure):

• The first block of $a$'s must match the second block of $a$'s ($a^m \dots a^m$).
• The first block of $b$'s must match the second block of $b$'s ($b^n \dots b^n$).

A single stack cannot maintain both of these independent, overlapping relationships simultaneously. Thus, $L_2$ is not context-free (it is a classic context-sensitive language).

3. Language $L_3 = \{a^m b^n \mid m = 2n + 1\}$

For $L_3$, the number of $a$'s is exactly twice the number of $b$'s plus one. We can construct a CFG for this language as follows:

Since we can generate $L_3$ using a CFG, $L_3$ is context-free.

Thus, only $L_1$ and $L_3$ are context-free languages.