GATE CS 2004 Q87 — Regular and Context-free Languages

The given language is $L = \{a^m b^n c^{m+n} \mid m, n \geq 1\}$.

1. Why is $L$ not Regular?
To recognize strings in $L$, we need to remember the count of $a$'s ($m$) and $b$'s ($n$) to ensure that the number of $c$'s is exactly $m+n$. Since $m$ and $n$ can be arbitrarily large, a Finite Automaton (which has finite memory) cannot keep track of these counts. Thus, $L$ is not regular.

2. Why is $L$ Context-Free?
We can design a Pushdown Automaton (PDA) that uses a single stack to accept $L$ as follows:

• For every $a$ read from the input, push a symbol $A$ onto the stack.
• For every $b$ read from the input, push a symbol $B$ onto the stack. At this point, the stack contains $m$ copies of $A$ at the bottom and $n$ copies of $B$ on top.
• When $c$'s start arriving:
  • Pop a $B$ for each of the first $n$ $c$'s.
  • Pop an $A$ for each of the next $m$ $c$'s.
• If the input is completely consumed and the stack is empty (except for the initial stack symbol), accept the string.

Therefore, the language is context-free but not regular.