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: