Closure Properties of Context Free Languages - Theory of Computation -

Closure Properties of Context Free Languages

Context-free grammars and pushdown automata - a brief reminder

Context-free languages are the languages generated by context-free grammars (CFGs) and accepted by pushdown automata (PDAs). A context-free grammar has productions that replace a single non-terminal by a (possibly empty) string of terminals and non-terminals.

\(A \to \rho\) where \(A \in N\) and \(\rho \in (T \cup N)^*\)

Here \(N\) denotes the set of non-terminals and \(T\) the set of terminals. Informally, a PDA can use its stack to compare one pair of quantities (for example, the number of \(a\)'s against the number of \(b\)'s). This limitation underlies several closure and non-closure results for CFLs.

Properties of Context-free Languages

Union

Statement: If \(L_1\) and \(L_2\) are context-free, then \(L_1 \cup L_2\) is context-free.

Construction idea using CFGs: given grammars \(G_1\) and \(G_2\) with start symbols \(S_1\) and \(S_2\), form a new grammar with a fresh start symbol \(S\) and the additional productions \(S \to S_1 \mid S_2\). This produces a CFG for the union.

\(S \to S_1 \mid S_2\)

Construction idea using PDAs: given NPDAs for \(L_1\) and \(L_2\), create a new NPDA that nondeterministically chooses to simulate either the NPDA for \(L_1\) or the NPDA for \(L_2\).

Example (preserved):

\(L_1 = \{\, a^n b^n c^m \mid m \ge 0,\; n \ge 0 \,\}\)

\(L_2 = \{\, a^n b^m c^m \mid n \ge 0,\; m \ge 0 \,\}\)

\(L_3 = L_1 \cup L_2 = \{\, a^n b^n c^m \mid m \ge 0,\; n \ge 0 \,\} \;\cup\; \{\, a^n b^m c^m \mid n \ge 0,\; m \ge 0 \,\}\)

Both \(L_1\) and \(L_2\) are context-free; their union is therefore context-free.

Concatenation

Statement: If \(L_1\) and \(L_2\) are context-free, then the concatenation \(L_1 \cdot L_2\) is context-free.

Construction idea using CFGs: if \(G_1\) and \(G_2\) have start symbols \(S_1\) and \(S_2\), create a new grammar with start symbol \(S\) and the production \(S \to S_1 S_2\).

\(S \to S_1 S_2\)

Construction idea using PDAs: build an NPDA that nondeterministically simulates the NPDA for \(L_1\); on an accepting configuration it switches (via \(\varepsilon\)-move) to simulate the NPDA for \(L_2\).

Example (preserved):

\(L_1 = \{\, a^n b^n \mid n \ge 0 \,\}\)

\(L_2 = \{\, c^m d^m \mid m \ge 0 \,\}\)

\(L_3 = L_1 \cdot L_2 = \{\, a^n b^n c^m d^m \mid n \ge 0,\; m \ge 0 \,\}\)

This language can be recognised by a PDA that first pushes for \(a\)'s and pops for \(b\)'s, then pushes for \(c\)'s and pops for \(d\)'s.

Kleene closure (Kleene star)

Statement: If \(L\) is context-free then \(L^*\) (the Kleene closure of \(L\)) is context-free.

Construction idea using CFGs: given a grammar for \(L\) with start symbol \(S_1\), add a new start symbol \(S\) with productions \(S \to S_1 S \mid \varepsilon\). This derives any finite concatenation of strings from \(L\).

\(S \to S_1 S \mid \varepsilon\)

Example (preserved):

\(L = \{\, a^n b^n \mid n \ge 0 \,\}\)

\(L^* = \{\, a^{n_1} b^{n_1} a^{n_2} b^{n_2} \cdots a^{n_k} b^{n_k} \mid k \ge 0,\; n_i \ge 0 \,\}\)

Intersection with regular languages

Statement: If \(L\) is context-free and \(R\) is regular, then \(L \cap R\) is context-free.

Construction idea: simulate a nondeterministic PDA for \(L\) together with a deterministic finite automaton (DFA) for \(R\) in a product construction. The combined machine keeps the PDA's stack and the DFA's current state; it accepts exactly those strings accepted by both machines, so the intersection is accepted by a PDA and hence is context-free.

Homomorphism and inverse homomorphism

Statement: Context-free languages are closed under homomorphism and inverse homomorphism.

Definitions and construction ideas:

• Homomorphism: a homomorphism \(h\) is defined by images of terminals and extended to strings by concatenation. If \(L\) is generated by a grammar, apply \(h\) to every terminal occurrence in the grammar to obtain a grammar for \(h(L)\).
• Inverse homomorphism: for a homomorphism \(h\), the preimage \(h^{-1}(L) = \{\, w \mid h(w) \in L \,\}\) of a CFL \(L\) is also context-free; one can construct a PDA that nondeterministically expands each letter according to \(h\) and simulates the PDA for \(L\).

Reversal

Statement: If \(L\) is context-free then the reversal \(L^R = \{ w^R \mid w \in L\}\) is context-free.

Construction idea using CFGs: for every production \(A \to X_1 X_2 \cdots X_k\) in the grammar for \(L\), include \(A \to X_k \cdots X_2 X_1\) in a grammar for \(L^R\). The resulting grammar generates the reversals of strings of \(L\).

Intersection (general) and complementation - non-closure

Statement: Context-free languages are not closed under arbitrary intersection and are not closed under complementation.

Counterexample idea (preserved example): take

\(L_1 = \{\, a^n b^n c^m \mid n \ge 0,\; m \ge 0 \,\}\)

\(L_2 = \{\, a^m b^n c^n \mid m \ge 0,\; n \ge 0 \,\}\)

Then

\(L_1 \cap L_2 = \{\, a^n b^n c^n \mid n \ge 0 \,\}\)

The language \(\{\, a^n b^n c^n \mid n \ge 0 \,\}\) is a standard non-context-free language (a PDA cannot ensure three equal counts). Hence the intersection of two CFLs can be non-CFL.

Reason for non-closure under complement: if CFLs were closed under complement then they would be closed under intersection (via De Morgan: \(L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}\)), which contradicts the previous counterexample. Therefore complement of a CFL need not be a CFL.

Difference

Statement: Context-free languages need not be closed under set difference. Because \(L_1 - L_2 = L_1 \cap \overline{L_2}\), non-closure of complement and intersection implies non-closure of difference in general.

Summary table (informal)

• Closed: union, concatenation, Kleene star, homomorphism, inverse homomorphism, reversal, intersection with regular languages.
• Not necessarily closed: intersection (general), complementation, difference.

Deterministic context-free languages (DCFLs)

Definition: A deterministic context-free language is a language accepted by a deterministic pushdown automaton (DPDA) - the machine has at most one possible move at any configuration (no nondeterminism).

Properties (key facts preserved and expanded):

• DCFLs form a proper subset of CFLs: every DCFL is CFL, but some CFLs are not deterministic (for example, unions of certain CFLs may require nondeterminism).
• DCFLs are closed under complementation: if \(L\) is deterministic context-free then \(\overline{L}\) is also deterministic context-free.
• DCFLs are closed under inverse homomorphism.
• DCFLs are closed under intersection with regular languages (product construction with a DFA preserves determinism of the control part when combined carefully).
• DCFLs are not closed under union, concatenation or Kleene star in general; nondeterminism is often required to implement these operations.

Illustrative remark (preserved):

\(L_1 = \{\, a^n b^n c^m \mid n \ge 0,\; m \ge 0 \,\}\) is deterministic context-free because a DPDA can push on \(a\)'s, pop on \(b\)'s, and ignore the trailing \(c\)'s.

\(L_3 = L_1 \cup L_2\) where \(L_2 = \{\, a^n b^m c^m \mid n \ge 0,\; m \ge 0 \,\}\) (the union from earlier) is context-free but not deterministic context-free in general because a DPDA cannot always decide, on reading the input, which pattern to follow (whether to match \(a\)'s with subsequent \(b\)'s or to match \(b\)'s with subsequent \(c\)'s) without lookahead or nondeterminism.

Proof sketches and constructions - pedagogical notes

When asked to show closure formally in an exam, give one of the following constructive arguments depending on the operation:

• Provide a grammar construction (for union, concatenation, Kleene star, reversal, homomorphism).
• Provide a PDA construction (for union, concatenation, Kleene star, intersection with regular languages): explain how to combine machines using \(\varepsilon\)-moves or a product construction.
• Provide a reduction or counterexample (for non-closure): demonstrate two CFLs whose intersection or difference yields a known non-CFL such as \(\{a^n b^n c^n \mid n \ge 0\}\).

Worked examples (recap of preserved examples)

Example 1 - Union:

\(L_1 = \{\, a^n b^n c^m \mid n \ge 0,\; m \ge 0 \,\}\)

\(L_2 = \{\, a^n b^m c^m \mid n \ge 0,\; m \ge 0 \,\}\)

\(L_1 \cup L_2\) is context-free by the grammar construction \(S \to S_1 \mid S_2\).

Example 2 - Concatenation:

\(L_1 = \{\, a^n b^n \mid n \ge 0 \,\}\)

\(L_2 = \{\, c^m d^m \mid m \ge 0 \,\}\)

\(L_1 \cdot L_2\) is context-free by the grammar construction \(S \to S_1 S_2\) or by concatenating PDAs with an \(\varepsilon\)-transition between them.

Example 3 - Non-closure of intersection:

\(L_1 = \{\, a^n b^n c^m \mid n \ge 0,\; m \ge 0 \,\}\)

\(L_2 = \{\, a^m b^n c^n \mid m \ge 0,\; n \ge 0 \,\}\)

\(L_1 \cap L_2 = \{\, a^n b^n c^n \mid n \ge 0 \,\}\) which is not context-free.

Final remarks

In summary, context-free languages enjoy several closure properties useful for constructions and proofs (union, concatenation, Kleene star, homomorphisms, inverse homomorphisms, reversal, and intersection with regular languages), but they fail to be closed under some set operations such as arbitrary intersection and complementation. Deterministic CFLs form a smaller class with stronger properties in some directions (notably closure under complement) but do not inherit all CFL closure properties.