• Nechť L1, L2 jsou
dva bezkontextové jazyky.
• Potom existují dvě
BKG G1, G2, pro které platí:
L(G1) = L1, L(G2) = L2;
• Sestrojme gramatiky pomocí předchozích
algoritmů:
• Gu, pro kterou platí: L(Gu) = L(G1) È L(G2)
• Gc, pro kterou platí: L(Gc) = L(G2) . L(G2)
• Gi, pro kterou platí: L(Gi) = L(G1)*
• Každá BKG definuje bezkontextový jazyk, tedy:
L1 L2, L1 È L2, L1* jsou bezkontextové jazyky.