Closure Properties

Learn about the closure properties of deterministic and nondeterministic context-free languages.

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 S1S_1 and S2S_2 are the respective start variables for context-free languages L1L_1 and L2L_2. We can form a CFG for L1  L2L_1 \cup \; L_2 as follows:

Get hands-on with 1200+ tech skills courses.