ВУЗ:
Составители:
193
ными. От регулярного выражения можно всегда перейти к таблице
переходов-выходов автомата. Процедуру этого перехода будем ил-
люстрировать на примере ниже.
Рассмотрим вопрос перехода от описательной формы задания
алгоритмов работы конечных автоматов к представлению их в виде
регулярных выражений. Основная идея такого перехода заключается
в следующем. Составляются регулярные выражения для событий
,
которые наиболее часто встречаются в инженерной практике синтеза
цифровых устройств. Эти события принимаются за основные. С по-
мощью операций дизъюнкции, умножения и итерации из основных
событий могут быть составлены другие более сложные события, со-
ответствующие заданному алгоритму работы автомата.
Приведем пример системы основных событий.
1.
Событие, состоящее из всех слов входного алфавита, всеоб-
щее событие: F={х
1
∨х
2
∨…∨х
m
}.
2.
Событие, включающее все возможные слова, состоящие из
символов x
i1
, x
i2
, …, x
ip
: S={х
i1
∨х
i2
∨…∨х
ip
}.
3.
Событие, содержащее все слова, оканчивающиеся буквой x
i
:
S={х
1
∨х
2
∨…∨х
m
}x
i
=Fx
i
.
4.
Событие, содержащее все слова, оканчивающиеся отрезком
слова l: S=Fl.
5.
Событие, состоящее из всех слов, имеющих начальный и ко-
нечный отрезки l
1
и l
2
соответственно: S=l
1
F l
2
.
6.
Событие, содержащее все слова, в которых хотя бы один раз
встречается отрезок слова l
1
в любом месте: S=F⋅l
1
⋅F.
7.
Событие, содержащее только однобуквенные слова входного
алфавита: S=х
1
∨х
2
∨…∨х
m
.
8.
Событие, содержащее только двухбуквенные слова входного
алфавита: S=(х
1
∨
х
2
∨
…
∨
х
m
)
⋅
(х
1
∨
х
2
∨
…
∨
х
m
).
Страницы
- « первая
- ‹ предыдущая
- …
- 195
- 196
- 197
- 198
- 199
- …
- следующая ›
- последняя »
