6.Closure Properties§

\(L=\{a^nb^n | n>0\}\), \(LL = \{a^nb^na^mb^m | n>0, m>0 \}\)

Theorem: CFL’s are closed under union, concatenation, and star-closure.

Given: 2 CFGs \(G_1 = (V_1,T_1,S_1,P_1)\) and \(G_2 = (V_2,T_2,S_2,P_2)\)

Union

Construct \(G_3\) such that \(L(G_3) = L(G_1) \cup L(G_2)\).
\(G_3 = (V_3,T_3,S_3,P_3)\)
\(V_3 = V_1 \cup V_2 \cup \{S_3\}, T_3 = T_1 \cup T_2\), and
\(P_3 = P_1 \cup P_2 \cup \{S_3 \rightarrow S_1 | S_2 \}\).

Concatenation

Construct \(G_3\) such that
\(L(G_3) = L(G_1)L(G_2)\).
\(G_3 = (V_3,T_3,S_3,P_3)\)
\(V_3 = V_1 \cup V_2 \cup \{S_3\}, T_3 = T_1 \cup T_2\), and
\(P_3 = P_1 \cup P_2 \cup \{S_3 \rightarrow S_1S_2 \}\).

Star-Closure

Construct \(G_3\) such that \(L(G_3) = L(G_1)^*\)
\(G_3 = (V_3,T_3,S_3,P_3)\)
\(V_3 = V_1 \cup \{S_3\}, T_3 = T_1\), and
\(P_3 = P_1 \cup P_2 \cup \{S_3 \rightarrow S_1S_3|\lambda \}\).

Intersection

Theorem: CFL’s are NOT closed under intersection

Let \(L_1 = \{a^nb^nc^m | n,m > 0\}\) and
\(L_2 = \{a^nb^mc^m | n,m> 0\}\)
\(L_1\) and \(L_2\) are CFLs
Then \(L_1 \cap L_2 = \{a^nb^nc^n | n >0 \}\) is not CFL.

Complementation

Theorem: CFL’s are NOT closed under complementation.

Set identity:

\(L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}\)

Thus, CFLs are not closed under complementation.

Example for theorem below:

\(L_1 = \{a^nb^ma^n \mid m> 0, n>0 \}\)
\(L_2 = \{w \mid w \in{\Sigma}^{*}\) and \(w\) has an even
number of b’s}, \(\Sigma = \{a,b\}\),
\(L_1 \cap L_2 = \{a^nb^mb^ma^n\}\) is a CFL.

Regular Intersection (1)

CFL’s are closed under regular intersection. If \(L_1\) is CFL and \(L_2\) is regular, then \(L_1 \cap L_2\) is CFL.

Proof: (sketch)

This proof is similar to the construction proof in which we showed regular languages are closed under intersection.

We can take a NPDA for \(L_1\) and a DFA for \(L_2\) and construct a NPDA for \(L_1 \cap L_2\).

Some Decision Problems for CFGs

For a given CFG \(G\), is \(L(G)\) empty?

A: Remove useless productions. Then, is \(S\) useless?

For a given CFG \(G\), is \(L(G)\) infinite?

A: Is there a repeating variable?

For two given CFGs \(G_1\) and \(G_2\), does \(L(G_1) = L(G_2)\)?

A: There is no general algorithm that can always deterimine if two CFG generate the same language!

A Richer Grammar

Here is a grammar for \(L = \{a^nb^nc^n \mid n \geq 1 \}\).

\(S \rightarrow abc \mid aAbc\)
\(Ab \rightarrow bA\)
\(Ac \rightarrow Bbcc\)
\(bB \rightarrow Bb\)
\(aB \rightarrow aa \mid aaA\)

Consider how to derive \(a^3b^3c^3\)

This is called a Context Sensitive Grammar