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

UptoLike

ВУЗ: 

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

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

Рубрика: 

47
нение можно заменить применением одного правила 5а, относящегося к построению
таблицы выходов синтезируемого автомата Мили.
Правило 5а. Таблица выходов автомата Мили имеет те же обозначения строк и
столбцов, что и построенная по правилу 4 таблица его переходов. На пересечении
произвольной строки, обозначенной буквой входного алфавита х
i
, и произвольного
столбца, обозначенного состоянием i
1
∨ i
2
∨... ∨ i
k
(k ≥ 1), в таблице выходов ставится
выходной сигнал (R
j1
, ..., R
jm
), состоящий из символов всех тех регулярных вы-
ражений R
1
, ..., R
P
, конечные места которых х
i
-следуют хотя бы за одним из мест i
1
,
i
2
,..., i
k
. В столбце, обозначенном пустым состоянием, во всех строках ставится пустой
выходной сигнал ( ).
Алгоритм, состоящий из правил 1, 2, 3, 4, 5а, будем называть особым алго-
ритмом синтеза конечных автоматов Мили. Этот алгоритм допускает отождеств-
ление соответственных мест в нулевом комплексе исходных регулярных выражений,
полученном по правилам 1 и 2 основного алгоритма. Что же касается подобных мест,
то, ввиду отсутствия в рассматриваемом случае отметок состояний, их необходимо
заменить так называемыми квазиподобными местами, определяемыми следующим
образом.
Основные места α
1
, ..., α
k
любого заданного комплекса регулярных выражений
называются квазиподобными, если для любой буквы х входного алфавита комплекса
К множество конечных мест комплекса, х-следующих за основными местами
α
1
,..., α
k
, совпадают между собой, а множества М
1
, ..., М
k
основных мест ком-
плекса, х-следующих за местами α
1
, ..., α
k
либо одинаковы, либо становятся одинако-
выми после замены входящих в множества М
1
, ..., М
k
мест α
2
, ..., α
k
местом α
1
.
Сформулируем правило отождествления мест в случае синтеза автоматов Мили.
Правило 2б. При синтезе автоматов Мили к нулевому комплексу К
0
, получен-
ному по правилам 1–2 основного алгоритма синтеза, можно применять последова-
тельно, шаг за шагом, но в любом порядке операции отождествления соответствен-
ных и квазиподобных мест. К полученному в результате таких отождествлений ком-
плексу применяются правила 3, 4, 5а особого алгоритма синтеза конечных автоматов
Мили.
Согласно приведенному правилу, квазиподобными являются все тупиковые
места комплекса, т. е. такие его основные места, которые не связаны ни одной буквой
входного алфавита ни с одним местом комплекса. Если в синтезированном автомате
Мили имеются состояния, образуемые основными индексами лишь одних тупиковых
мест, то в таблице переходов автомата столбцы, обозначенные всеми такими состоя-
ниями, будут состоять из одних символов пустого состояния *, а соответствующие
столбцы в таблице выходов – из одних лишь символов пустого выходного сигнала.
При синтезе автоматов Мили наряду с правилом 2б может применяться следующее
правило (2в).
Правило 2в. При синтезе автоматов Мили тупиковым основным местам в ком-
плексе регулярных выражений можно не присваивать никаких основных индексов.
Алгоритмы синтеза, использующие правила 1, 2, 2б, 2в, 3, 4, 5а, будем назы-
вать усовершенствованными особыми алгоритмами синтеза конечных автома-
тов Мили.
Усовершенствованные алгоритмы синтеза автоматов Мили, в отличие от ос-
новного алгоритма, не приводят к автоматам, в которых заданные события представ-
лены множеством состояний, а лишь к таким автоматам, в которых эти события пред-

Страницы