**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, *L*_{1} and *L*_{2}.
Let the grammar *G*_{1} = (*N*_{1},
*T, S*_{1}, *P*_{1}) such that
*L*(*G*_{1}) = *L*_{1}, and let the
grammar *G*_{2} = (*N*_{2}, *T, S*_{2}, *P*_{2})
such that *L*(*G*_{2}) = *L*_{2}.
Without loss of generality we can suppose that *N*_{1} ∩ *N*_{2} = ∅.
We are going to give the context-free grammars *G _{Un}*,

Union

To create the grammar

*G*we need a new start symbol S, such that_{Un}*S*∩*N*_{1}=*S*∩*N*_{2}=*S*∩*T*= ∅. Then, let*G*= (_{Un}*N*_{1}∪*N*_{2}∪ {*S*},*T, S, P**1*∪*P*_{2}∪ {*S*→*S*,_{1}*S*→*S*_{2}}).Concatenation

For the grammar

*G*we also need a new start symbol S, such that_{Co}*S*∩*N**1*=*S*∩*N*_{2}=*S*∩*T*= ∅. Then, let*G*= (_{Co}*N*_{1}∪*N*_{2}∪ {*S*},*T, S, P*_{1}∪*P*_{2}∪ {*S*→*S*_{1}*S*_{2}}).Kleene star

For the grammar

*G*we again use a new start symbol S, where_{Kl}*S*∩*N*_{1}=*S*∩*T*= ∅. Then, let*G*= (_{Kl}*N*_{1}∪ {*S*},*T, S, P**1*∪ {*S*→ λ,*S*→*SS*_{1}}).

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 *L*_{1} = {*a ^{i}b^{i}c^{j}*∣

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 *L*_{1} and *L*_{2} 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 *L*_{1} be a context-free language,
and let *L*_{2} be a regular language, where
*L*_{2} = *L*_{21} ∪ *L*_{22}
∪...∪ *L*_{2}* _{n}*,
and where each

because intersection distributes over union. Since context-free languages are closed under union, we only have to show that
*L*_{1} ∩ *L*_{2}* _{i}*
is context-free for each

*S'*→*A*_{[}_{q}_{0,}_{S,}_{qf}_{]}∈*P'*,*A*_{[}_{q}_{1,}_{B,}_{q3}_{]}→*A*_{[}_{q}_{1,}_{C,}_{q2}_{]}*A*_{[}_{q}_{2,}_{D,}_{q3}_{]}∈*P'*for each possible*q*_{1},*q*_{2},*q*_{3}∈*Q*, if*B*→*CD*∈*P*,*A*_{[}_{q}_{1,}_{B,}_{q2}_{]}→*a*∈*P'*if*B*→*a*∈*P*and δ(*q*_{1},*a*) =*q*_{2},*S'*→ λ ∈*P'*, if λ ∈*L*_{1}and*q*_{0}=*q*._{f}

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
*L*_{2}* _{i}* as well.
Each production rule of the grammar

QED.