Official PYQ · 2016Set 2 · Q43Context-free Grammars and Push-down AutomataMCQ1 mark

GATE CS 2016 Set 2 Q43 — Context-free Grammars and Push-down Automata

Consider the following languages:

$L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$
$L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$

Which one of the following is TRUE?

View worked solution

Answer: B

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

1. Analysis of $L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}$

We can rewrite the condition for the number of $c$ 's as $n + m$ . Since the $a$ 's appear first, followed by $b$ 's, and then $c$ 's, we can match the $c$ 's with the $b$ 's first, and then with the $a$ 's.

PDA Intuition (LIFO Stack):

Push all $n$ $a$ 's onto the stack.
Push all $m$ $b$ 's onto the stack.
For each incoming $c$ , pop a symbol from the stack. The first $m$ $c$ 's will pop the $m$ $b$ 's, and the subsequent $n$ $c$ 's will pop the $n$ $a$ 's.
If the stack becomes empty precisely when the input is fully consumed, the string is accepted.

Since this can be processed using a single stack, $L_1$ is a Context-Free Language (CFL).

Context-Free Grammar (CFG) for $L_1$ :

\begin{aligned} S &\to aSc \mid aAc \\ A &\to bAc \mid bc \end{aligned}

Here, $S$ generates $a^n A c^n$ and $A$ generates $b^m c^m$ , resulting in $a^n b^m c^{m+n}$ . Thus, $L_1$ is context-free.

2. Analysis of $L_2 = \{a^n b^n c^{2n} : n \ge 1\}$

In $L_2$ , there are two independent comparisons that must be maintained simultaneously:

The number of $a$ 's must equal the number of $b$ 's.
The number of $c$ 's must be twice the number of $a$ 's (or $b$ 's).

A single stack cannot keep track of both comparisons. If we use the stack to match $a$ 's and $b$ 's, the stack becomes empty before we can verify the count of $c$ 's.

Using the Pumping Lemma for CFLs:

Let $p$ be the pumping length. Choose the string $z = a^p b^p c^{2p} \in L_2$ .
Any partition $z = uvwxy$ with $|vwx| \le p$ and $|vx| \ge 1$ cannot contain all three symbols ( $a$ , $b$ , and $c$ ).
If $vx$ contains only $a$ 's and $b$ 's, pumping it changes the counts of $a$ and $b$ but leaves the count of $c$ unchanged, violating the $c^{2n}$ relation.
If $vx$ contains only $b$ 's and $c$ 's, pumping it changes the counts of $b$ and $c$ but leaves the count of $a$ unchanged, violating the $a^n b^n$ relation.