Consider the following two languages over the alphabet \(\{a, b, c\}\), where \(m\) and \(n\) are natural numbers.
\[ L_1 = \{a^m b^m c^{m+n} \mid m, n \ge 1\} \]
\[ L_2 = \{a^m b^n c^{m+n} \mid m, n \ge 1\} \]
Which ONE of the following statements is CORRECT?
Answer
(C)
Explanation
- \(L_2\) is context-free: \(a^m b^n c^{m+n} = a^m\,(b^n c^n)\,c^m\) is a nested pattern, generated by \(S \to aSc \mid aAc\), \(A \to bAc \mid bc\). A PDA pushes one symbol for every \(a\) and \(b\) and pops one for every \(c\).
- \(L_1\) is not context-free: it needs \(\#a = \#b\) and also \(\#c \gt \#a\) (because \(n \ge 1\)), so the same count \(m\) must be compared twice, but the single stack is used up matching the a's against the b's.
- Pumping lemma check: take \(a^p b^p c^{p+1}\). The pumped part (length \(\le p\)) cannot touch both a's and c's. If it contains a's or b's, pumping up gives \(\#a \ne \#b\) or \(\#a = \#b \ge p + 1 = \#c\); if it contains only c's, pumping down gives \(\#c \le p = \#a\). Either way the string leaves \(L_1\).
Answer: C