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