7.2. Closure Properties for CFLs¶
7.2.1. 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)\)
7.2.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 \}\).
7.2.3. 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 \}\).
7.2.4. 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 \}\).
7.2.5. Intersection¶
Theorem: CFL’s are NOT closed under intersectionLet \(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 CFLsThen \(L_1 \cap L_2 = \{a^nb^nc^n | n >0 \}\) is not CFL.
7.2.6. 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.
7.2.7. 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.
7.2.8. 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.
7.2.9. 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!
7.2.10. 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
