Лекции::

Дополнительно:

Методы абстрактного синтеза

Чтобы система переходов автомата была определенной, для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. Например, для регулярного события S1 первая буква x1 переводит автомат из начального состояния 0 в состояние 1, вторая буква x2 – из 1 в 2.

S = | x1| x2 | v | x1| x1| x1|

      0    1     2   0   1   3    4

S = | x1| x2 | x2 | v | x2| x2|

      0    1     2    5    0    6    7

Поскольку первая буква второго слова x1x1x1, входящего в S1 также есть x1, то она переводит автомат из начального состояния 0 в 1. Вторая буква x1 переводит автомат из 1 в 3, третья – из 3 в 4.

Первые две слова x1x2x2, входящего в  S2, совпадают с первым словом события S1. Поэтому первые две буквы этого слова должны последовательно переводить автомат из 0 в 1, и из 1 в 2. Дальнейшие состояния обозначим числами 5, 6 и 7. Получившаяся в результате форма записи определяет разметку мест регулярных выражений.

Местами регулярного выражения называют промежутки между двумя буквами, между буквой и знаком дизъюнкции, а так же между буквой и скобкой. Кроме того, вводят начальное место, обозначаемое цифрой 0 и конечные места, отождествляемые с концом каждого слова. Для запрещенного события Sзапр последовательность событий можно не назначать.

Для размеченных регулярных выражений составляется отмеченная таблица переходов.

e

e

y1

e

y1

y2

e

y2

E

xj\ai

0

1

2

3

4

5

6

7

*

x1

1

3

*

4

*

*

*

*

*

x2

6

2

5

*

*

*

7

*

*

Чтобы система переходов автомата была определена при подаче любого входного слова, кроме состояний 0 ё 7, вводится еще одно состояние, которое обозначается звездочкой *. В это состояние автомат переходит при подаче входных слов, которые не входят в события S1 и  S2. Выходным сигналом y1 отмечены состояния 2 и 4, y2 – состояния 5 и 7. Остальные состояния отмечены пустой буквой e.

предыдущаяследующая