3.7 Closure properties of context-free languages

Context-free languages have cool properties that let us combine and modify them while keeping them context-free. We can mix and match languages using union, concatenation, and Kleene star, and still end up with context-free languages.

These closure properties are super useful for proving languages are context-free and building grammars for complex languages. We can break big problems into smaller pieces and use these properties to put them back together.

Closure Properties of Context-Free Languages

Key Closure Properties

Top images from around the web for Key Closure Properties

• 

  Regular expression - Wikipedia View original

  Is this image relevant?

• 

  CS 340: Lecture 4: Context-Free Languages, Parsing, Ambiguity View original

  Is this image relevant?

• 

  Context-free grammar - Wikipedia View original

  Is this image relevant?

• 

  Regular expression - Wikipedia View original

  Is this image relevant?

• 

  CS 340: Lecture 4: Context-Free Languages, Parsing, Ambiguity View original

  Is this image relevant?

1 of 3

Top images from around the web for Key Closure Properties

• 

  Regular expression - Wikipedia View original

  Is this image relevant?

• 

  CS 340: Lecture 4: Context-Free Languages, Parsing, Ambiguity View original

  Is this image relevant?

• 

  Context-free grammar - Wikipedia View original

  Is this image relevant?

• 

  Regular expression - Wikipedia View original

  Is this image relevant?

• 

  CS 340: Lecture 4: Context-Free Languages, Parsing, Ambiguity View original

  Is this image relevant?

1 of 3

• Context-free languages are closed under union $L_1 \cup L_2$ combines two context-free languages $L_1$ and $L_2$ into a single context-free language
• Context-free languages are closed under concatenation $L_1 \cdot L_2$ forms a new context-free language by concatenating strings from $L_1$ and $L_2$
• Context-free languages are closed under Kleene star $L^*$ forms a new context-free language by allowing any number of concatenations of strings from $L$
• Context-free languages are closed under substitution $s(L)$ replaces each terminal symbol in one context-free language with another context-free language
• Context-free languages are closed under homomorphism $h(L)$ maps each symbol in the alphabet of $L$ to a string over another alphabet, forming a new context-free language

Additional Closure Properties

• Context-free languages are closed under inverse homomorphism $h^{-1}(L)$ the preimage of a context-free language $L$ under a homomorphism $h$
• Context-free languages are closed under intersection with regular languages $L \cap R$ forms a new context-free language by intersecting a context-free language $L$ with a regular language $R$
• Context-free languages are not closed under intersection $L_1 \cap L_2$ the intersection of two context-free languages is not always context-free
• Context-free languages are not closed under complement $\overline{L}$ the complement of a context-free language is not always context-free

Proving Closure of Context-Free Languages

Proving Closure Under Union, Concatenation, and Kleene Star

• To prove closure under union, construct a new context-free grammar that includes all productions from the grammars of $L_1$ and $L_2$ and a new start symbol $S$ that derives either of the original start symbols $S_1$ or $S_2$ $(S \rightarrow S_1 | S_2)$
• To prove closure under concatenation, construct a new context-free grammar that includes all productions from the grammars of $L_1$ and $L_2$ and a new start symbol $S$ that derives the concatenation of the original start symbols $S_1$ and $S_2$ $(S \rightarrow S_1S_2)$
• To prove closure under Kleene star, construct a new context-free grammar that includes all productions from the original grammar of $L$ and a new start symbol $S$ that derives either the empty string or the concatenation of the original start symbol $S_L$ and the new start symbol $S$ $(S \rightarrow \varepsilon | S_LS)$

Proving Closure Under Substitution, Homomorphism, and Inverse Homomorphism

• To prove closure under substitution, replace each terminal symbol $a$ in the productions of one context-free grammar $G_1$ with the start symbol $S_2$ of another context-free grammar $G_2$
• To prove closure under homomorphism, apply the homomorphism function $h$ to each symbol in the productions of the original context-free grammar $G$, creating a new grammar $G'$ with productions $h(A \rightarrow \alpha) = h(A) \rightarrow h(\alpha)$
• To prove closure under inverse homomorphism, construct a new context-free grammar that generates strings that, when the homomorphism $h$ is applied, belong to the original context-free language $L$

Proving Closure Under Intersection with Regular Languages

• To prove closure under intersection with regular languages, construct a new context-free grammar by intersecting the productions of the original context-free grammar $G$ with the states and transitions of a finite automaton $M$ recognizing the regular language $R$
• The new grammar will have nonterminals of the form $(A, q)$, where $A$ is a nonterminal from $G$ and $q$ is a state from $M$, and productions of the form $(A, q) \rightarrow (B, r)(C, s)$ if $A \rightarrow BC$ is a production in $G$ and $M$ has transitions $q \rightarrow r$ and $r \rightarrow s$ on the corresponding terminals

Constructing Grammars for Closed Languages

Constructing Grammars for Union, Concatenation, and Kleene Star

• To construct a context-free grammar for the union of two context-free languages $L_1$ and $L_2$, create a new start symbol $S$ and productions $S \rightarrow S_1 | S_2$, where $S_1$ and $S_2$ are the start symbols of the grammars for $L_1$ and $L_2$, respectively
• To construct a context-free grammar for the concatenation of two context-free languages $L_1$ and $L_2$, create a new start symbol $S$ and productions $S \rightarrow S_1S_2$, where $S_1$ and $S_2$ are the start symbols of the grammars for $L_1$ and $L_2$, respectively
• To construct a context-free grammar for the Kleene star of a context-free language $L$, create a new start symbol $S$ and productions $S \rightarrow \varepsilon | S_LS$, where $S_L$ is the start symbol of the grammar for $L$

Constructing Grammars for Substitution, Homomorphism, and Inverse Homomorphism

• To construct a context-free grammar for the substitution of context-free languages, replace each terminal symbol $a$ in the productions of one grammar $G_1$ with the start symbol $S_2$ of another grammar $G_2$
• To construct a context-free grammar for the homomorphic image of a context-free language, apply the homomorphism function $h$ to each symbol in the productions of the original grammar $G$, creating a new grammar $G'$ with productions $h(A \rightarrow \alpha) = h(A) \rightarrow h(\alpha)$
• To construct a context-free grammar for the inverse homomorphic image of a context-free language, create productions that generate strings that, when the homomorphism $h$ is applied, belong to the original language $L$

Constructing PDAs for Languages Obtained Through Closure Operations

• To construct a PDA for a language obtained through closure operations, design the PDA to simulate the behavior of the context-free grammar constructed for that language
• The PDA will have states corresponding to the nonterminals of the grammar and transitions based on the productions of the grammar
• The PDA will accept a string if it can simulate a derivation of that string in the grammar

Applications of Closure Properties

Proving Context-Freeness and Simplifying Grammar Construction

• Use closure properties to prove that a language obtained through a combination of closure operations on context-free languages is also context-free
• For example, if $L_1$ and $L_2$ are context-free, then $L_1 \cup L_2$, $L_1 \cdot L_2$, and $L_1^*$ are also context-free
• Apply closure properties to simplify the construction of context-free grammars or PDAs for complex languages by breaking them down into simpler languages and combining them using appropriate closure operations
• For instance, to construct a grammar for $L = \{a^nb^nc^n | n \geq 0\} \cup \{a^nb^{2n} | n \geq 0\}$, construct separate grammars for $L_1 = \{a^nb^nc^n | n \geq 0\}$ and $L_2 = \{a^nb^{2n} | n \geq 0\}$ and then combine them using the union closure property

Analyzing Language Structure and Solving Decision Problems

• Utilize closure properties to analyze the structure and properties of context-free languages, such as determining whether a language is infinite or has certain substrings
• For example, if $L$ is context-free and infinite, then $L^*$ is also infinite and context-free
• Use closure properties to solve decision problems related to context-free languages, such as determining whether a given string belongs to a language obtained through closure operations
• For instance, to determine if a string $w$ belongs to $L_1 \cup L_2$, check if $w$ belongs to either $L_1$ or $L_2$

Optimizing and Transforming Grammars and PDAs

• Apply closure properties to optimize or transform context-free grammars or PDAs by exploiting the properties of the closure operations used to define the language
• For example, if a language $L$ is defined as the homomorphic image of a simpler language $L'$, construct a grammar or PDA for $L'$ and then apply the homomorphism to obtain a grammar or PDA for $L$
• Use closure properties to remove unnecessary nonterminals or productions from a grammar or simplify the transitions in a PDA while preserving the language generated or accepted