Correctness of CFL Closure / Automaton Statements (CFLs, DPDA, Complement)

This question asks which statement among (i)–(iv) is true. For context-free languages (CFLs) we rely on closure properties and language–machine characterizations.

Key background:

• A context-free language (CFL) is closed under some operations (e.g., union, concatenation, intersection with regular sets) and not under others (e.g., complement).
• CFLs are exactly the languages recognized by (nondeterministic) pushdown automata (PDA).
• A deterministic pushdown automaton (DPDA) recognizes a strict subclass of CFLs: the deterministic context-free languages (DCFLs).

We will evaluate each statement:

• (i) Intersection of two CFLs is context-free: false in general.
• (ii) Every CFL can be accepted by a DPDA: false (not all CFLs are deterministic CFLs).
• (iii) Union of two CFLs is context-free: true.
• (iv) Complement of a CFL is context-free: false in general.

The only true statement is (iii). (A formal justification appears below with grammars/closure theorems and standard counterexamples.)

Mermaid schematic:

Language classes and operations used in the problem

Context-free grammar (CFG) ↔ PDA:

• CFLs can be generated by CFGs and recognized by NPDA.

DCFL is the deterministic subclass:

• DPDA constraints make the machine less powerful than nondeterministic PDA, so not every CFL is deterministic.

Important closure facts you use for this question:

• Closure under union is true.
• Closure under complement is false in general.
• Closure under intersection is false in general; however, CFLs are closed under intersection with regular languages.

Statement-by-statement conclusions

(i) The intersection of two CFLs is context-free

Claim: $L_1, L_2$ CFL $\Rightarrow L_1 \\cap L_2$ is CFL.
Result: False in general.

Reason (high level): CFLs are not closed under intersection for arbitrary CFL operands. While you can always do intersection when one language is regular (because regular constraints can be carried through pushdown computation), doing it for two arbitrary CFLs can require more power than a single stack context-free mechanism can provide.

Key takeaway term set:

• Closure under intersection with regular languages
• Intersection of CFLs
• Non-determinism

(ii) Every CFL can be accepted by a DPDA

Claim: CFL $\subseteq$ DCFL.
Result: False.

Reason (high level): DPDA recognizes exactly DCFL, which is a strict subset of CFLs. If every CFL were accepted by a DPDA, then every CFL would be deterministic, collapsing the known hierarchy between CFL and DCFL.

Key takeaway term set:

• DCFL
• Deterministic vs nondeterministic PDA
• Strict subset

(iii) The union of two CFLs is context-free

Claim: $L_1, L_2$ CFL $\Rightarrow L_1 \\cup L_2$ is CFL.
Result: True.

Reason (constructive): Given CFGs $G_1=(V_1,\\Sigma,P_1,S_1)$ for $L_1$ and $G_2=(V_2,\\Sigma,P_2,S_2)$ for $L_2$, create a new start symbol $S$ and grammar $G$ with productions:

• $S \\to S_1 \\mid S_2$
• plus all productions of $P_1$ and $P_2$ (renaming variables if needed to avoid collisions).

This grammar generates exactly the strings in $L_1$ or $L_2$.

Key takeaway term set:

• CFG
• Start symbol
• Union construction

(iv) The complement of a CFL is context-free

Claim: $L$ CFL $\Rightarrow \\Sigma^*\\setminus L$ CFL.
Result: False in general.

Reason (high level): CFLs are not closed under complement. Thus, taking complements can produce languages that cannot be recognized by any pushdown automaton.

Key takeaway term set:

• Complement
• Not closed under complement
• CFL limitations