Question 53

Analyze $L_1 = \{a^n b^m c^{n+m} \mid m, n \ge 1\}$:
Notice that $c^{n+m}$ contains $m + n$ copies of $c$. We can recognize $L_1$ with a deterministic pushdown automaton (DPDA):

1. Push each incoming $a$ onto the stack (recording $n$).
2. Push each incoming $b$ onto the stack (recording $m$).
3. For each incoming $c$, pop a $b$ from the stack until all $b$'s are matched, then continue popping an $a$ for each subsequent $c$ until all $a$'s are matched.
4. If the stack is empty exactly when the input ends, accept.
   Because a PDA with a single stack accepts $L_1$, $L_1$ is context-free (in fact, a deterministic CFL). A CFG for $L_1$ is:

Analyze $L_2 = \{a^n b^n c^{2n} \mid n \ge 1\}$:
Here, the number of $a$'s, $b$'s, and $c$'s are all tied to the same count $n$. A pushdown automaton cannot simultaneously verify that the number of $a$'s equals the number of $b$'s and that the number of $c$'s equals twice that number using a single stack.

Applying the Pumping Lemma for CFLs to $L_2$: Let $p$ be the pumping length and choose $z = a^p b^p c^{2p} \in L_2$. Any decomposition $z = uvwxy$ with $|vwx| \le p$ and $|vx| \ge 1$ can contain at most two distinct symbols among $\{a, b, c\}$. Pumping $v$ and $x$ alters the counts of at most two symbol types while leaving the third unchanged, producing strings not in $L_2$. Hence, $L_2$ is not context-free.

Therefore, $L_1$ is context-free while $L_2$ is not context-free.