Теория и реализация языков программирования


         

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


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

Теорема 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|n
1}.

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


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





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