Введение в схемы, автоматы и алгоритмы



             

Теорема о разрастании для автоматных языков - часть 2


  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.




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