В некоторых случаях для определения

В некоторых случаях для определения того, является ли язык регулярным, может быть полезным необходимое условие, которое называется леммой Огдена о разрастании.

Теорема 3.4. (Лемма о разрастании для регулярных множеств). Пусть L - регулярное множество. Существует такая константа k, что если

и , то цепочку w можно представить в виде xyz, где и для всех .

Доказательство. Пусть M = (Q, ?, D, q0, F) - конечный автомат, допускающий L, то есть L(M) = L и k = |Q|. Пусть и . Рассмотрим последовательность конфигураций, которые проходит автомат M, допуская цепочку w. Так как в ней по крайней мере k + 1 конфигурация, то среди первых k+1 конфигурации найдутся две с одинаковыми состояниями. Таким образом, получаем существование такой последовательности тактов, что



для некоторых . Отсюда . Но тогда для любого i > 0 автомат может проделать последовательность тактов Таким образом, для всех i 1. Случай i = 0 то есть также очевиден.

С помощью леммы о разрастании можно показать, что не является регулярным множеством язык L={0n1n|n1}.

Допустим, что L регулярен. Тогда для достаточно большого n0n1n можно представить в виде xyz, причем y e и для всех i 0. Если или , то . Если , то . Получили противоречие. Следовательно, L не может быть регулярным множеством.


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

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---