Примеры абстрактного синтеза автоматов по регулярным выражениям

Абстрактный синтез автомата выполняется в следующей последовательности [1,3]:

• составляются регулярные выражения, представляющие события,

• по регулярным выражениям находится таблица переходов и выходов автомата Мура,

• минимизируется число внутренних состояний автомата Мура,

• модель Мура заменяется моделью Мили,

• минимизируется число внутренних состояний автомата Мили.

Пример 1. На вход абстрактного автомата (рис.1.1) S_4.1 с входным алфавитом X = {x₀, x₁, x₂} и выходным алфавитом Y = {y₁, y₂}, предварительно установленного в исходное состояние, последовательно во времени поступает триада символов. Входные последовательности символов разбиты на две группы: A-триады и B-триады. A-триады заданы следующим списком: x₀x₀x₁, x₁x₂x₂, x₀x₂x₁. Все остальные триады являются B-триадами. Если на вход автомата приходит A-триада, то он вырабатывает сигнал y₁ и останавливается. Если же подается какая-нибудь B-триада, то автомат выдает сигнал y₂ и тоже останавливается. Из состояний останова автомат выводится специальным сигналом, не принадлежащим алфавиту X.

Синтезируемый автомат распознает A-триады и B-триады. Он работает как автомат однократного действия. Алгоритм работы этого автомата можно записать в виде двух регулярных выражений:

(1.1)

где событие H₁ соответствует принадлежности входной триады к A-группе и представлено в автомате выходным сигналом y₁, а событие H₂, представленное сигналом y₂, описывает B-триады. Запись H₂ = означает, что событие H₂ наступает во всех случаях, когда входная триада не принадлежит к событию H₁. Событие H₂ можно представить и выражением, аналогичным по форме выражению для H₁, но в данном случае это только усложнит синтез.

Регулярные выражения позволяют построить отмеченную таблицу состояний автомата Мура по методике, изложенной . В общих чертах идею перехода от регулярных выражений к табличному заданию автомата можно пояснить следующим образом. Множество событий тесно связано с множеством выходных сигналов. Выходные сигналы автомата Мура зависят только от состояний автомата. Каждому событию можно поэтому поставить в соответствие конкретное состояние автомата Мура. Различные подмножества множества событий, которые не представляют ни одно из событий, можно считать пустым множеством событий. Если множество событий пусто, то автомат выдает пустое выходное слово e. Пустое выходное слово может выдаваться автоматом во многих состояниях.

Состояния автомата можно обозначать буквами, буквами с цифровыми индексами или просто индексами. Последний вариант удобнее. Начальное состояние автомата обозначим цифрой 0, остальные внутренние состояния автомата – десятичными числами 1, 2, 3 и так далее.

Выполним разметку основных мест регулярных выражений (4.1) для события H₁:

.

(1.2)

Индекс 0 выражения (1.2) относится к началу каждого из трех термов, заключенных в круглые скобки. Буква x₀ переводит автомат из нулевого состояния в состояние 1, следующая буква x₀ – из состояния 1 в состояние 2 и так далее. В состояниях 3, 6 и 9 автомат формирует выходной сигнал y₁ (смотрите (1.1)). Эти состояния являются подобными и их можно обозначить одним индексом. Тогда получим новую разметку мест с уменьшенным числом состояний автомата:

.

(1.3)

Анализируя выражение (1.3), замечаем, что состояния 1 и 7 являются соответственными и их можно обозначить одинаковыми индексами. В самом деле, если автомат находился в состоянии 0 и на его входе появилась буква x₀, то ее можно рассматривать как начало слова x₀x₀x₁ или как начало слова x₀x₂x₁. Очевидно, что реакция автомата на букву x₀ должна быть одинаковой. После замены индекса 7 на индекс 1 и переобозначения состояния 8 в состояние 6, получим окончательную разметку основных мест:

.

(1.4)

По выражению (1.4) с учетом (1.1) и требований к синтезируемому автомату составлена отмеченная таблица 1 состояний автомата Мура. В табл. 1 звездочкой обозначено еще одно состояние, которое принято называть тупиковым. В состояние  автомат попадает в тех случаях, когда он принимает слово события H₂. Например, если в состоянии 0 на вход приходит буква x₂, то автомат переключается в конечное состояние , потому что в словах x₀x₀x₁, x₁x₂x₂ и x₀x₂x₁ события H₁ первая буква либо x₀, либо x₁, а не x₂. Переход автомата в состояние  приводит к формированию выходного сигнала y₂. Состояния 0, 1, 2, 4, 5 и 6 отмечены пустым выходным сигналом e. Это объясняется тем, что, например, состояние 5 автомата соответствует лишь части слова x₁x₂x₂ события H₁. Если следующая буква будет x₂, то автомат перейдет в конечное состояние 3. Если же вместо x₂ на входе появится буква x₀ или буква x₁, то автомат переключится в другое конечное состояние – состояние  . После приема сочетания x₁x₂ еще пока не известно, будет ли триада отнесена к группе A или к группе B.

Таблица 1

Первый вариант отмеченной таблицы состояний автомата S_4.1 (модель Мура)

Выходной	e	e	e	y1	e	e	e	y2
сигнал
Состоя-	0	1	2	3	4	5	6	
ние
Входной
сигнал
x0	1	2		3				
x1	4		3	3			3	
x2		6		3	5	3		

Обозначим состояние  индексом 7 и получим табл.2

Таблица 2

Второй вариант таблицы состояний автомата S_4.1

Выходной	e	e	e	y1	e	e	e	y2
сигнал
Состоя-	0	1	2	3	4	5	6	7
ние
Входной
сигнал
x0	1	2	7	3	7	7	7	7
x1	4	7	3	3	7	7	3	7
x2	7	6	7	3	5	3	7	7

Из табл. 2 видим, что состояния 2 и 6 эквивалентны, так как выходные сигналы в этих состояниях одинаковы, а входные сигналы вызывают переходы в одни и те же состояния. Заменяя индекс 6 на индекс 2, индекс 7 на индекс 6 и удаляя из табл.2 столбец для состояния 6, получим табл. 3

Таблица 3

Третий вариант таблицы состояний автомата S_4.1 (модель Мура)

Выходной	e	e	e	y1	e	e	y2
сигнал
Состоя-	0	1	2	3	4	5	6
ние
Входной
сигнал
x0	1	2	6	3	6	6	6
x1	4	6	3	3	6	6	6
x2	6	2	6	3	5	3	6

В общем случае модель Мура имеет избыточное число состояний по сравнению с моделью Мили, поэтому преобразуем автомат Мура в автомат Мили и попытаемся минимизировать число его состояний. Интерпретация автомата Мура, заданного отмеченной таблицей состояний, как автомата Мили выполняется в следующей последовательности:

• индексы всех состояний сохраняются;

• в клетки совмещенной таблицы состояний автомата Мили переносятся выходные сигналы, которые соответствуют индексам состояний отмеченной таблицы состояний автомата Мура.

Выполнив указанные преобразования, получим табл. 4

Таблица 4

Совмещенная таблица состояний автомата S_4.1 (модель Мили)

Состоя-	0	1	2	3	4	5	6
ние
Входной
сигнал
x0	1/e	2/e	6/y2	3/y1	6/y2	6/y2	6/y2
x1	4/e	^6/y2	3/y1	3/y1	6/y2	6/y2	6/y2
x2	6/y2	2/e	6/y2	3/y1	5/e	3/e	6/y2

Одна из клеток табл. 4 помечена символом . Эту часть таблицы следует понимать так: если автомат находится в состоянии 1 и входной сигнал равен x₁, то формируется выходной сигнал y₂, а после переключения автомат перейдет в состояние 6. Явно эквивалентных состояний автомата S_4.1 в табл. 4 нет, поэтому уменьшить число состояний автомата простым способом не удается.

Примечание. Символ пустого сигнала e в совмещенных таблицах состояний автоматов Мили в дальнейшем писать не будем.

На рис. 1 изображен орграф автомата S_4.1, построенный по табл. 4, который дает более наглядное представление о работе автомата, чем таблица состояний.

Рис.4.1.Орграф автомата Мура S_4.1 однократного действия

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