Введение в схемы, автоматы и алгоритмы
Теорема о разрастании для автоматных языков - часть 2
- Предположим, что L автоматный язык. Тогда для него имеется константа n из утверждения теоремы ref{th-razr}.
- Определим по n некотрое "специальное" слово w из L длины > n и докажем, что для любого разбиения w = xyz, удовлетворяющего условиям (1) и (2) теоремы, найдется такое k 0, что слово wk=xyk z не принадлежит L.
- На основании полученного противоречия делаем вывод, что L - не автоматный язык.
Разумеется, в этой схеме самым сложным является выбор "специального" слова w в пункте (2). Что касается, подбора такого k
