GATE CS 2006 Q19 — Context-free Grammars and Push-down Automata

To determine which of the languages are not context-free, let us analyze each one individually:

• Language $L_1 = \{0^{n+m}1^n0^m \mid n,m \geq 0\}$:
  We can rewrite the string format as $0^m 0^n 1^n 0^m$ because the leading $0^{n+m}$ can be split into $0^m 0^n$. Since all these symbols are $0$, they commute.
  We can easily construct a Context-Free Grammar (CFG) for $L_1$: $$\begin{align*} S &\to 0S0 \mid A \\ A &\to 0A1 \mid \epsilon \end{align*}$$ Here, $S$ generates the outer $0^m \dots 0^m$ and $A$ generates the inner $0^n 1^n$. Thus, $L_1$ is context-free.
• Language $L_2 = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$:
  Let $k = n+m$. Since $n \geq 0$, we have $k \geq m$. Thus, the language can be written as: $$L_2 = \{0^k 1^k 0^m \mid k \geq m \geq 0\}$$ This requires a PDA to match the number of leading $0$s with the number of $1$s (requiring stack operations), and simultaneously ensure that the number of trailing $0$s ($m$) is less than or equal to $k$. Since a PDA cannot perform these multiple overlapping comparisons, $L_2$ is not context-free.
• Language $L_3 = \{0^{n+m}1^{n+m}0^{n+m} \mid n,m \geq 0\}$:
  Let $k = n+m$. Since $n, m \geq 0$, $k$ can be any non-negative integer. Thus, the language simplifies to: $$L_3 = \{0^k 1^k 0^k \mid k \geq 0\}$$ This is a classic non-context-free language (similar to $a^n b^n c^n$). Thus, $L_3$ is not context-free.

Therefore, $L_2$ and $L_3$ are NOT context-free.