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

UptoLike

ВУЗ: 

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

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

Рубрика: 

192
При абстрактном синтезе конечных автоматов важную роль иг-
рают регулярные события. Любое событие, которое можно получить
из символов входного алфавита с помощью конечного числа опера-
ций дизъюнкций, произведения и итерации, называется регулярным
событием, а выражения, составленные с помощью этих операций,
называют регулярными выражениями.
Для данного алфавита Х={x
1
, x
2
, …, x
m
} регулярное выражение
определяется рекурсивно следующим образом:
1) входное слово, состоящее из одного символа x
i
, 1≤i≤m, или сим-
вола l (пустое слово) является регулярным выражением;
2) если β
1
и β
2
— регулярные выражения, то β
1
∨β
2
, β
1
β
2
, β
1
* также
регулярные выражения.
Операции дизъюнкции и умножения удовлетворяют дистрибу-
тивным законам
β
1
⋅(β
2
∨ β
3
) = β
1
β
2
∨ β
1
β
3
и (β
2
∨ β
3
)⋅β
1
= β
2
β
1
∨ β
3
β
1
.
Приведем пример регулярного выражения
(х
1
х
2
∨ х
3
)⋅(х
3
∨ х
2
х
4
) = х
1
х
2
х
3
∨ х
1
х
2
х
2
х
4
∨ х
3
х
3
∨ х
3
х
2
х
4
,
определяющего конечное множество входных слов. А выражение
(х
1
х
1
∨ х
2
х
2
)*={l, х
1
х
1
, х
2
х
2
, х
1
х
1
х
1
х
1
, х
1
х
1
х
2
х
2
, х
2
х
2
х
1
х
1
, х
2
х
2
х
2
х
2
,
х
1
х
1
х
1
х
1
х
1
х
1
...}
не явно задает бесконечное множество входных слов. Не является
регулярным событием множество всех последовательностей вида
х
1
х
1
… х
1
х
2
таких, что их длина выражается простым числом.
В теории конечных автоматов доказано, что любые регулярные
выражения и только они представимы в конечных автоматах.
Любое событие, состоящее из конечного множества слов, явля-
ется регулярным. Такое событие можно представить в виде дизъ-
юнкции всех входящих в него слов. События, состоящие из беско-
нечного числа слов, могут быть как регулярными, так и нерегуляр-

Страницы