ВУЗ:
Составители:
196
Эта форма называется
разметкой мест регулярных
выражений. Местом регуляр-
ного выражения называются
промежутки между двумя бу-
квами, между буквой и знаком дизъюнкции, а также между буквой и
скобкой. Кроме того, вводят начальное место и конечные места,
отождествляемые с концом каждого слова.
Для рассматриваемого примера состояние
0 – начальное; со-
стояния
2, 4, 5, 7 – конечные.
По размеченным регулярным выражениям составляем отмечен-
ную таблицу переходов автомата Мура. Для этого выясняем вопрос о
том, в какое состояние переходит автомат, если на его вход посту-
пают различные входные символы (табл.
5.20).
Если для данного со-
стояния
s
k
в размеченном вы-
ражении нет символа
х
i
,
стоящего справа от состоя-
ния, то переход
δ(s
k
,х
i
) будет
неопределенным. Значение
функции
λ(s
i
) будет равно y
k
, если автомат переходит в s
i
при вход-
ном слове
P
j
, принадлежащем S
k
. В результате получаем исходную
отмеченную таблицу переходов. Далее эту таблицу можно упростить
(один формальный метод такого упрощения рассмотрен в подразделе
5.2). Сейчас же попытаемся упростить (минимизировать) табл. 5.20
неформальным способом.
Если в таблице есть одинаковые столбцы, то можно оставить
только один из них и перенумеровать оставшиеся состояния. В табл.
S
1
=
х
1
х
2
∨
х
1
х
1
х
1
0 1 2 0 1 3 4 y
1
S
2
=
х
1
х
2
х
2
∨
х
2
х
2
0 1 2 5 0 6 7 y
2
Таблица 5.20
y
3
y
3
y
1
y
3
y
1
y
2
y
3
y
2
0 1 2 3 4 5 6 7
х
1
1 3
∗
4
∗ ∗ ∗ ∗
х
2
6 2 5
∗ ∗ ∗
7
∗
Страницы
- « первая
- ‹ предыдущая
- …
- 198
- 199
- 200
- 201
- 202
- …
- следующая ›
- последняя »
