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

Теорема 9.5.1.

Неверно, что для любых контекстно-свободных языков L1

и L2

язык

тоже контекстно-свободный.

Доказательство. Положим

и . В примере 9.2.1 было доказано, что язык

не является контекстно-свободным.

Теорема 9.5.2.

Неверно, что для любого контекстно-свободного языка

язык

тоже контекстно-свободный.

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

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

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

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

не является контекстно-свободным?