Сучкова Л.И. Абстрактный и структурный синтез автоматов

Подождите немного. Документ загружается.

Пусть автоматы А

и А

допускают регулярные языки L

и L

Для того чтобы построить автомат A, распознающий

язык L=L

∪L

, необходимо удалить циклы из начальных со-

стояний автоматов L

и L

, а затем объединить новые началь-

ные состояния автоматов.

Для удаления циклов из начального состояния при зада-

нии автомата графом вводится одно дополнительное состоя-

ние, которое будет начальным, и из него проводятся дуги по

тем символам в те вершины, куда они шли из старого на-

чального состояния. Например, пусть задан конечный

авто-

мат, распознающий язык b*cd*, представленный на рисунке

1.5,а. В начальном состоянии а

данного автомата имеется

цикл. В общем случае отсутствие петли в начальном состоя-

нии не означает отсутствия цикла, проходящего через на-

чальное состояние. Для удаления цикла добавляем в граф

еще одну вершину, делаем ее начальной. Если старое на-

чальное состояние было также заключительным, то и новое

начальное состояние будет заключительным. Так

как из ста-

рого начального состояния были переходы по символам “b” и

“c”, то необходимо построить дуги из нового начального со-

стояния в те вершины, куда были переходы при чтении сим-

волов “b” и “c” (рисунок 1.5,б).

Рисунок1.5

Рассмотрим пример построения автомата, распознающе-

го объединение регулярных языков a* и b*. Если выполнять

объединение без удаления циклов из начальных состояний

автоматов, распознающих а* и b*, то получим автомат (рису-

нок 1.6), который может распознавать и считать правильны-

ми «смешанные» цепочки вида “bbaabaaa”, которые не при-

надлежат ни одному из исходных регулярных языков. По-

этому удаление циклов обязательно при построении автома

та, распознающего объединение регулярных языков. Авто-

мат, распознающий язык L=a*∪b*, представлен на рисунке

1.6.

Рисунок1.6

Для построения автомата, распознающего язык L=L

необходимо проверить 2 аспекта: имеются ли циклы в за-

ключительных состояниях A

и в начальном состоянии A

Если циклы имеются в обоих случаях, то их необходимо уда-

лить. Если циклов нет, либо они имеются только в одном

случае, то все заключительные состояния автомата A

допол-

няем экземпляром автомата A

. Начальным состоянием ре-

зультирующего автомата A будет начальное состояние A

, а

заключительными состояниями – заключительные состояния

Удаление циклов в заключительном состоянии осущест-

вляется введением дополнительной вершины, которая станет

заключительной, и проведением в нее дуг по тем символам и

из тех вершин, из которых шли дуги в старое заключительное

состояние. Для автомата b*cd* результат удаления циклов из

заключительной вершины представлен на рисунке 1.7.

Рисунок1.7

Пример построения автомата

, распознающего произве-

дение языков b*cd* и a

, приведен на рисунке 1.8.

Рисунок1.8

Для построения автомата A, распознающего итерацию

регулярного языка L

, необходимо удалить циклы из началь-

ного и заключительных состояний A

и объединить началь-

ное и все заключительные состояния в одну вершину.

Построим автомат, распознающий итерацию b*cd*. На

рисунке 1.9,а приведен автомат, распознающий b*cd* без

циклов в начальном и заключительном состояниях. На ри-

сунке 1.9,б начальная и заключительная вершины объедине-

ны, что соответствует распознаванию (b*cd*)*.

Рисунок1.9

Для построения автомата А, распознающего усеченную

итерацию

регулярного языка L

, строим A как произведение

* и A

(умножение справа) или как произведение A

и A

(умножение слева) автоматов, распознающих произведение

итерации языка L

и самого языка L

. Умножение слева или

справа зависит от наличия циклов в начальных и заключи-

тельных состояниях А

. Если у А

нет циклов в начальном

состоянии, то целесообразно использовать умножение спра-

ва, а если нет циклов в заключительных состояниях – то ум-

ножение слева.

Рассмотрим пример синтеза конечного автомата-

распознавателя, допускающего язык (а*bc

)*∪b*d

. Будем

строить автомат по шагам, в соответствии с правилами син-

теза.

Автоматы, распознающие языки L={a} и L=a*, пред-

ставлены на рисунке 1.10.

Рисунок1.10

Автоматы, распознающие языки b, c

и bc

представле-

ны на рисунке 1.11.

Рисунок1.11

Далее необходимо построить автомат, распознающий

произведение языков а* и bc

. У первого автомата есть цикл

в заключительном состоянии, а у второго нет цикла в на-

чальном. Это значит, что можно не выполнять удаление цик-

лов, а просто в заключительное состояние первого автомата

дорисовать экземпляр второго автомата. После этого заклю-

чительными состояниями нового автомата будут заключи-

тельные состояния второго автомата. Автомат,

распознаю-

щий язык а*bc

, приведен на рисунке 1.12.

Рисунок1.12

Этот автомат имеет циклы в начальном и заключитель-

ном состояниях, что недопустимо при построении автомата,

распознающего итерацию языка а*bc

. Будем удалять циклы

из начального состояния (рисунок 1.13), а затем из заключи-

тельного состояния (рисунок 1.14).

Рисунок1.13

Рисунок1.14

У автомата, приведенного на рисунке 1.14, нет циклов в

начальном и заключительном состояниях, а значит, можно

построить новый автомат, распознающий итерацию языка,

объединив начальное и заключительное состояния (рисунок

1.15).

Рисунок1.15

Так как автомат, распознающий (а*bc

)* в дальнейшем

будет использован для построения автомата, распознающего

объединение языков, удалим циклы из его начального со-

стояния. Результат удаления приведен на рисунке 1.16.

Рисунок1.16

Автомат, распознающий язык b*d

, приведен на рисунке

1.17.

Рисунок1.17

Так как он содержит цикл в начальном состоянии и

нужно строить автомат, распознающий объединение языков,

то необходимо избавиться от циклов в начальном состоянии.

Результат удаления цикла из начального состояния приведен

на рисунке 1.18.

Рисунок1.18

Объединив начальные состояния автоматов на рисунках

1.16 и 1.18, получим автомат, распознающий язык

(а*bc

)*∪b*d

(рисунок 1.19).

Автоматы-распознаватели, полученные в результате

синтеза, могут быть недетерминированными, что предпола-

гает переход при получении некоторого входного сигнала

необязательно в единственное состояние.

Рисунок 1.19

Для каждого недетерминированного конечного автома-

та-распознавателя существует эквивалентный ему детерми-

нированный автомат-распознаватель.

Рассмотрим алгоритм детерминизации конечного авто-

мата-распознавателя. Для этого нужно построить таблицу

переходов для недетерминированного автомата, причем все

состояния автомата обозначить числовыми индексами. Затем

строится таблица переходов для детерминированного авто-

мата, начиная с начального состояния. Если в клетке таблицы

находятся несколько состояний, то в таблицу заносится но-

вое

состояние, индекс которого получен объединением ин-

дексов состояний, расположенных в этой клетке. При этом

индексы при их объединении должны возрастать. В таблицу

переходов нового автомата заносятся только те состояния, в

которые есть переход, начиная из начального. Строки табли-

цы для новых состояний, индексы которых получены объе-

динением индексов, заполняем следующим

образом. Пусть

надо заполнить строку для состояния

i1i2…im

, тогда для ка-

ждого распознаваемого символа запишем в соответствующий

ему столбец таблицы состояние, полученное объединением

индексов состояний, стоящих в клетках i

, i

, …, i

. Заключи-

тельными состояниями нового автомата будут те состояния,

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

ний недетерминированного автомата.

Рассмотрим пример. Пусть задан недетерминированный

автомат-распознаватель, приведенный на рисунке 1.20.

Рисунок 1.20