Синтез цифровых автоматов. Захаров Н.Г - 47 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

46
одном из выражений R
1
,…, R
p
, входящее в место α, с каким-либо основным местом
того же самого выражения, входящим в место β. При этом место β q-следует за ме-
стом α.
Основные места в данном комплексе К регулярных выражений называются со-
ответственными, если множества слов входного алфавита, связывающих начальное
место комплекса с каждым из этих мест, одинаковы.
Основные места α
1
, …, α
k
в комплексе К называются подобными, если в
комплексе К им подчинены одинаковые множества конечных мест и если для
любой буквы х входного алфавита комплекса множества M
1
,
…, M
k
основных мест,
x-следующих за местами α
1
, …, α
k
, одинаковы, либо становятся одинаковыми при за-
мене входящих в них мест α
2
, …, α
k
местом α
1
.
Операция отождествления мест
Ее сущность заключается в том, что некоторому множеству основных мест
данного комплекса К, имеющих различные основные индексы, приписывается один и
тот же индекс k и, следовательно, все основные места в регулярных выражениях ком-
плекса, входившие в отождествляемые места комплекса К, составят новое основное
место комплекса, которое будет иметь основной индекс k.
Правила 1 и 2 основного алгоритма синтеза конечных автоматов применимы и
к заданному множеству регулярных событий некоторого комплекса К регулярных
выражений. В этом комплексе каждое основное место, за исключением начального
места, состоит из единственного основного места в выражениях R
1
, …, R
p
, состав-
ляющих комплекс. Таким образом, в комплексе К
0
не проводится никакого отождест-
вления мест, за исключением отождествления начальных мест, входящих в комплекс
выражений.
Все последующие правила (т. е. правила 3 – 6) основного алгоритма синтеза
автоматов оперируют с местами и с их индексами в этом комплексе К
0
, который бу-
дем называть нулевым. На практике оказывается возможным до перехода к правилам
3 – 6 применять к нулевому комплексу операцию отождествления мест так, что-
бы последующее применение правил 3 – 6 к новому комплексу привело к построе-
нию автоматов, представляющих исходные события R
1
, …, R
p
. Для этого правила
1 – 6 основного алгоритма синтеза конечных автоматов могут быть дополнены сле-
дующими правилами.
Правило 2а. К комплексу К
0
заданных регулярных выражений R
1
, …, R
p
, полу-
ченному по правилам 1 – 2, можно применять последовательно, шаг за шагом, опера-
цию отождествления соответственных мест и операцию отождествления подобных
мест. Последующие правила 3 – 6 применяются не к нулевому комплексу К
0
, а к ком-
плексу, полученному после выполнения любого числа таких отождествлений.
При практическом применении этого правила необязательно проводить все
возможные отождествления, достаточно ограничиться лишь некоторыми из них. Воз-
никающие таким образом алгоритмы (с тем или иным числом предварительных ото-
ждествлений мест) будем называть усовершенствованными алгоритмами синтеза
конечных автоматов.
Если стоит задача синтеза автомата Мили, то в общий алгоритм синтеза могут
быть внесены изменения, приводящие к уменьшению числа состояний синтезируемо-
го автомата. В данном случае нет необходимости отмечать состояния автомата в со-
ответствии с правилом 5 и затем применять правило 6: их последовательное приме-

Страницы