577
правок
Изменения
Нет описания правки
[[Файл:Enfa_before.jpg|left|thumb|240px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|240px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> недетерминированный автомат с <tex>\varepsilon-</tex>переходами следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова, "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex>(см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon-</tex>переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>cycle(L)</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|240px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|300px|Рис. 4. Автомат, принимающий язык <tex>cycle(L)</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.<br>
На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>cycle(L) = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.
