Suppose that \( L_1\) is a regular language and \( L_2\) is a context-free…

Answer: L1 - L2 is not necessarily context-free.

• L1 ∩ L2: This is always context-free. Intersection of a context-free language with a regular language yields a context-free language. Intuition: simulate the PDA for the context-free language while tracking the DFA state for the regular language (product construction).

• L1 · L2 (concatenation): This is always context-free. Concatenating a regular language with a context-free language preserves context-freeness. A PDA can simulate the regular part first (by converting the regular language to an NFA/PDA) and then switch to the PDA for the context-free part.

• L1 - L2 (set difference): This is not necessarily context-free.

  Reason: L1 - L2 = L1 ∩ complement(L2), and complements of context-free languages need not be context-free. Intersecting such a non-context-free complement with a regular language can yield a non-context-free language.

  Counterexample: Let the alphabet be {a,b}, take L1 = {a,b}* (regular) and L2 = { a^n b^n | n ≥ 0 } (context-free). Then L1 - L2 = {a,b}* \ { a^n b^n } is the complement of { a^n b^n }, which is known not to be context-free.

• L1 ∪ L2: This is always context-free. Union of a context-free language with a regular language is context-free. You can convert the regular language to a PDA and nondeterministically choose which PDA to run.