Consider the following languages: \(L_1 = {a^n b^m c^{n+m} : m,n ≥ 1}\) \(L_2…

Answer: L1 is context-free, and L2 is not context-free.

Show that L1 is context-free:

• A context-free grammar for L1 = {a^n b^m c^{n+m} : m,n ≥ 1} is:

• S → X Y

• X → a X c | a c

• Y → b Y c | b c

• Explanation: X generates a^n c^n (n≥1) and Y generates b^m c^m (m≥1). Concatenating gives a^n b^m c^{n+m}, so L1 is generated by this CFG and hence is context-free.

Show that L2 is not context-free:

• Let L2 = {a^n b^n c^{2n} : n ≥ 1}. Use the closure property: context-free languages are closed under inverse homomorphism.

• Define homomorphism φ by φ(a)=a, φ(b)=b, φ(d)=cc (and φ acts arbitrarily on other symbols if any).

• Compute the inverse image: φ^{-1}(L2) = {a^n b^n d^n : n ≥ 1}.

• But {a^n b^n d^n} is the standard non-context-free language (by the pumping lemma or other known results). Therefore φ^{-1}(L2) is not context-free.

• If L2 were context-free, its inverse homomorphic image φ^{-1}(L2) would also be context-free (closure property), a contradiction. Hence L2 is not context-free.

Conclusion: L1 is context-free (providing the grammar above), and L2 is not context-free (by inverse homomorphism and the known non-CFL {a^n b^n c^n}).