Which of the following statements is true ?

Answer: The union of two context-free languages is context-free.

• Proof sketch: Given context-free grammars G1 = (V1, Σ, R1, S1) and G2 = (V2, Σ, R2, S2), rename nonterminals so V1 and V2 are disjoint if needed. Construct a new grammar G = (V1 ∪ V2 ∪ {S}, Σ, R1 ∪ R2 ∪ {S → S1, S → S2}, S).

• Any string generated by G1 or G2 can be generated by G via S → S1 or S → S2, so L(G) = L(G1) ∪ L(G2). Thus union preserves context-freeness.

Why the other statements are false:

• The statement claiming a complement-related property is incorrect or ambiguous. In particular, context-free languages are not closed under complement in general.

• Counterexample for closure under complement: L = { a^n b^n | n ≥ 0 } is context-free, but its complement over the alphabet {a,b} is not context-free.

• Not every context-free language is accepted by a deterministic pushdown automaton. Deterministic context-free languages (DCFLs) are a strict subset of CFLs. For example, the language of palindromes over {a,b}* is context-free but cannot be recognized by a deterministic PDA because the machine cannot deterministically identify the middle of the string.

Therefore, only the statement that the union of two context-free languages is context-free is correct.