2020-05-25
94
Теорема 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}, что язык 
не является контекстно-свободным?
