Основы синтеза и диагностирования автоматов. Воронин В.В. - 199 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

Составители: 

Рубрика: 

195
S={х
2
∨
х
1
х
2
∨
х
1
х
1
х
2
} х
1
х
1
х
1
{х
1
} х
2
3
y
.
Это событие должно быть представлено в автомате символом
y
3
.
Если входное слово не принадлежит к
S
1
и S
2
, то оно обяза-
тельно принадлежит к
S
3
, которое должно быть представлено в авто-
мате выходным сигналом
y
2
.
S
3
=
2
21
y
SS
∨ .
Разработка абстрактного автомата по регулярным выражениям
(синтез абстрактного автомата) заключается в построении таблицы
переходов-выходов по этим выражениям. Синтез делится на два эта-
па: 1) получение исходных таблиц переходов и выходов; 2) миними-
зация числа внутренних состояний автомата. Автомат может синте-
зироваться как автомат Мура или Мили.
Синтез автомата прост, если
регулярные выражения не содер-
жат итерационных скобок, и сложен в противном случае. Рассмот-
рим синтез на простом примере. Пусть регулярные выражения авто-
мата имеют следующий вид
S
1
=х
1
х
2
∨х
1
х
1
х
1
1
y
;
S
2
=х
1
х
2
х
2
∨х
2
х
2
2
y
;
S
3
=
3
21 y
SS
∨ .
Обозначим начальное состояние –
0, а остальные – 1, 2, 3… .
Положим, что первый символ слова
х
1
х
2
∈ S
1
переводит автомат А из
0 в 1, второй символ – из 1 в 2. Первый символ слова х
1
х
1
х
1
∈ S
1
также будет переводить
А из 0 в 1, второй – из 1 в 3; третий – из 3 в
4. Первые две буквы слова х
1
х
2
х
2
∈ S
2
совпадают с первым словом S
1
.
Поэтому имеем
0 → 1; 1 → 2. После третьей буквы пусть состояние
2 переходит в 5. И, наконец, состояние, в которое А переходит при
подаче слова
х
2
х
2
, обозначим 6 и 7. Теперь все сказанное удобно
представить в следующем форме.

Страницы