L автоматный язык. Тогда для

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

Разумеется, в этой схеме самым сложным является выбор "специального" слова w в пункте (2). Что касается, подбора такого k 0, для которого wk L, то, как правило, достаточно рассмотреть k = 0 или k = 2.


Содержание  Назад  Вперед

---

---

---

---