• Let L1, L2 be two CFLs.
• Then, there exist two CFGs G1, G2 such that
L(G1) = L1, L(G2) = L2;
• Construct grammars
• Gu such that L(Gu) = L(G1) È L(G2)
• Gc such that L(Gc) = L(G2) . L(G2)
• Gi such that L(Gi) = L(G1)*
by
using the previous three algorithms
• Every CFG denotes CFL, so
• L1 L2, L1 È L2, L1* are CFLs.