Пересечение и дополнение контекстно-свободных языков

Теорема 9.5.1. Неверно, что для любых контекстно-свободных языков L₁ и L₂ язык тоже контекстно-свободный.

Доказательство. Положим и . В примере 9.2.1 было доказано, что язык не является контекстно-свободным.

Теорема 9.5.2. Неверно, что для любого контекстно-свободного языка язык тоже контекстно-свободный.

Доказательство. Положим , где . В примере 9.3.4 было доказано, что язык L является линейным (и следовательно, контекстно-свободным).

Упражнение 9.5.3. Является ли контекстно-свободным язык ?

Упражнение 9.5.4. Является ли контекстно-свободным язык ?

Упражнение 9.5.5. Существует ли такой линейный язык L над алфавитом {a,b}, что язык не является контекстно-свободным?