## 4.4. Closure Properties

Theorem 18. The context-free language class is closed under regular operations.

Proof. We are going to give a constructive proof for each regular operation one by one. We use two context-free languages, L1 and L2. Let the grammar G1 = (N1, T, S1, P1) such that L(G1) = L1, and let the grammar G2 = (N2, T, S2, P2) such that L(G2) = L2. Without loss of generality we can suppose that N1N2 = ∅. We are going to give the context-free grammars GUn, GCo and GKl, such that L(GUn) = L1L2, L(GCo) = L1 · L2 and L(GKl) = L1*.

1. Union

To create the grammar GUn we need a new start symbol S, such that SN1 = SN2 = ST = ∅. Then, let

GUn = (N1N2 ∪ {S}, T, S, P1P2 ∪ {SS1, SS2}).

2. Concatenation

For the grammar GCo we also need a new start symbol S, such that SN1 = SN2 = ST = ∅. Then, let

GCo = (N1N2 ∪ {S}, T, S, P1P2 ∪ {SS1S2}).

3. Kleene star

For the grammar GKl we again use a new start symbol S, where SN1 = ST = ∅. Then, let

GKl = (N1 ∪ {S}, T, S, P1 ∪ {S → λ, SSS1}).

QED.

Theorem 19. The context-free language class is not closed under intersection.

Proof. It is easy to prove this theorem, because we need only one counterexample. Let the language L1 = {aibicji, j ≥ 0}. L1 is context-free, because we have a context-free grammar G1 = ({S, A}, {a,b,c}, S, {SSc, SA, AaAb, A → λ}) such that L1 = L(G1). Let the language L2 = {aibjcji, j ≥ 0}. The language L2 is also context-free, because we have a context-free grammar G2 = ({S, A}, {a,b,c}, S, {SaS, SA, AbAc, A → λ}) such that L2 = L(G2). The intersection of these two languages is L1L2 = {ajbjcjj ≥ 0}, and in the Example 41 it is proven by the Bar-Hillel lemma that this language is not context-free.

QED.

Theorem 20. The context-free language class is not closed under the complement operation.

Proof. Now we use proof by contradiction. The set theoretical version of one of the well known De Morgan's laws says that With a slight modification, we have Suppose to the contrary that the context-free languages are closed under the complement operation. In this case, if L1 and L2 are context-free languages, the language defined by the right hand side of the expression must be context-free, however, since the left hand side may be non-context-free as in the previous theorem, a contradiction.

QED.

Theorem 21. The intersection of a context-free language and a regular language is always context-free.

Proof. We are going to give a constructive proof for this theorem. Let L1 be a context-free language, and let L2 be a regular language, where L2 = L21L22 ∪...∪ L2n, and where each L2i(1 ≤ in) is accepted by a deterministic finite automaton which has only one final state. We can do it without loss of generality, because it is well established fact that each regular language can be written in this form. Now

because intersection distributes over union. Since context-free languages are closed under union, we only have to show that L1L2i is context-free for each i. Let the grammar G = (N, T, S, P) be a Chomsky normal form grammar such that L(G) = L1 \ {λ}, and let DFAi = (Q, T, q0, δ, qf) be a deterministic finite automaton such that L(DFAi) = L2i. Now, we are going to define the context-free grammar G' = (N', T, S', P') such that L(G') = L1L2i. The set of the nonterminals of G' is N' = {A[q1,B,q2]∣ for each q1, q2Q, BN}. The production rules of the grammar G' are the following:

1. S'A[q0,S,qf]P',

2. A[q1,B,q3]A[q1,C,q2] A[q2,D,q3]P' for each possible q1, q2, q3Q, if BCDP,

3. A[q1,B,q2]aP' if BaP and δ(q1,a) = q2,

4. S' → λ ∈ P', if λ ∈ L1 and q0 = qf.

It is easy to see that the grammar G' generates the word p, if and only if it is generated by grammar G, and it is accepted by the automaton L2i as well. Each production rule of the grammar G' is context-free, so the language generated by the grammar G' is context-free.

QED.