8.2 Closure Properties and Decision Algorithms for
Context-Free Languages
In Chapter 4 we looked at closure under certain operations and algorithms to
decide on the properties of the family of regular languages. On the whole, the
questions raised there had easy answers. When we ask the same questions about
context-free languages, we encounter more difficulties. First, closure properties
that hold for regular languages do not always hold for context-free languages.
When they do, the arguments needed to prove them are often quite complicated.
Second, many intuitively simple and important questions about context-free
languages cannot be answered. This statement may seem at first surprising and
will need to be elaborated as we proceed. In this section, we provide only a
sample of some of the most important results.
Closure of Context-Free Languages
Theorem 8.3
The family of context-free languages is closed under union, concatenation, and
star-closure.
Proof: Let L 1 and L 2 be two context-free languages generated by the contextfree grammars G 1 = (V 1 , T 1 , S 1 , P 1 ) and G 2 = (V 2 , T 2 , S 2 , P 2 ), respectively. We
can assume without loss of generality that the sets V 1 and V 2 are disjoint.
Consider now the language L (G3), generated by the grammar
where S 3 is a variable not in V1 V2. The productions of G 3 are all the
productions of G 1 and G 2 , together with an alternative starting production that
allows us to use one or the other grammars. More precisely
Obviously, G 3 is a context-free grammar, so that L (G 3 ) is a context-free
language. But it is easy to see that