Closure Properties

Closure properties of nondeterministic CFLs

Since there is a difference between deterministic and non-deterministic context-free languages, there are differences in their closure properties. We first develop the closure properties for non-deterministic context-free languages, using CFG-based arguments. “Context-free-ness” is preserved under the following operations:

• Union.
• Concatenation.
• Kleene star.
• Regular intersection (intersection with a regular language).
• Regular union (union with a regular language).

Suppose $S_1$ and $S_2$ are the respective start variables for context-free languages $L_1$ and $L_2$. We can form a CFG for $L_1 \cup \; L_2$ as follows:

We introduced a new start variable, $S$, which recognizes the union of the two languages by providing a choice between the two original grammars. The rules for both grammars are part of the combined grammar, with variables renamed as needed to avoid name clashes.

A CFG for the concatenation $L_1L_2$ is equally straightforward:

To form a CFG for the Kleene star of $L_1$, we form a new grammar that generates the empty string and uses recursion for repetition:

For reversal, we only need to reverse all the right-hand sides in grammar. For example, consider the following grammar $S\to aSb \;|\; \lambda$ for the language $a^nb^n$. Reversing the right-hand sides gives the grammar $S\to bSa \;|\; \lambda$, which generates the language $b^na^n$.

Intuitively it makes sense that CFLs would not be closed under intersection in general, since it is unlikely that the stack operations of their respective PDAs would be compatible. The easiest way to show that CFLs are not closed under intersection is by means of a counterexample, where the intersection of two CFLs is not context-free. We will not prove here that the language $a^nb^nc^n$ is not context-free. Accepting that as a fact, note that for CFLs $L_1=\{a^nb^nc^m\mid n,m > 0\}$ ...