Doplněk: Není uzavřeno
Důkaz sporem:
Tvrzení: Třída bezkontextových jazyků není uzavřená vůči doplňku.
• Předpokládejme, že třída bezkontextových jazyků je uzavřená vůči doplňku:
• L1 = {ambncn: m, n ³ 1} je BKJ
• L2 = {anbncm: m, n ³ 1} je BKJ
• L1, L2  jsou tedy BKJ
• L1 È L2 je BKJ (třída BKJ je uzavřená vůči sjednocení)
• L1 È L2 je BKJ (předpoklad)
• De-Morganovy zákony říkají: L1 Ç L2 = {anbncn: n ³ 1} je BKJ
• {anbncn: n ³ 1} ale není BKJ Þ Spor
24/31