Теорема о накачке

Для регулярных языков

Прямое утверждение

Пусть R - регулярный язык. Тогда

Обратное утверждение

Для контекстно-свободных языков

Прямое утверждение

Пусть $L$ - контекстно-свободный язык. Тогда:

Доказательство

skip?

Обратное утверждение

• Следствие. Пересечение контекстно-свободных языков необязательно является контекстно-свободным языком
• Следствие. Дополнение до контестно-свободного языка необязательно является контекстно-свободным языком