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

UptoLike

ВУЗ: 

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

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

Рубрика: 

43
При этом каждое место β получает некоторое множество неосновных индексов.
Все индексы этого множества подписываются в произвольном порядке под верти-
кальной чертой, соответствующей месту β, ниже разделительной горизонтальной черты.
Все индексы (как основные, так и неосновные), относящиеся к любому
предосновному месту, заключаются в общую рамку.
4. Строится таблица переходов некоторого автомата Мура А. В качестве со-
стояний этого автомата берутся подмножества множества всех основных индексов.
При этом подмножество, состоящее из основных индексов i
1
,…, i
k
(k≥1), будем обо-
значать через i
1
∨ i
2
∨ … ∨ i
k
, а пустое множество основных индексов – звездочкой
(соответствующее ему состояние автомата А называется пустым).
Построение таблицы переходов с состояниями автомата А начинается с вписы-
вания обозначений строк и столбцов таблицы.
Строки таблицы обозначаются (в произвольном порядке) различными буквами
входного алфавита заданного множества событий.
Столбцы обозначаются состояниями автомата А, начиная с нулевого. После-
дующий столбец обозначается в произвольном порядке состоянием из предыдущего
столбца после вписывания всех состояний в этот столбец.
На пересечении произвольной (x
i
-й) строки и произвольного (q
j
-го) столбца
таблицы вписываются состояния (множества основных индексов), состоящие из ос-
новных индексов всех тех и только тех основных мест, которые x
i
-следуют за пре-
досновными местами, в числе индексов которых (как основных, так и не основных)
находится хотя бы один индекс, принадлежащий состоянию q
j
. В случае отсутствия
основных мест с требуемыми свойствами на соответствующем месте таблицы вписы-
вается пустое состояние.
5. Каждое из состояний i
1
∨ i
2
∨…∨ i
k
(k≥1), обозначающее столбцы таблицы
переходов, отмечается множеством (R
j1
, …, R
jm
) всех символов тех и только тех регу-
лярных выражений R
1
,…,R
p
, конечные места которых содержат в числе своих индек-
сов (как основных, так не основных) хотя бы один из индексов i
1
,…, i
k
.
Пустое состояние отмечается пустым множеством регулярных выражений
R
1
,…,R
p
и обозначается через ( ). С помощью введенных отметок, принимаемых за
выходной алфавит, строится отмеченная таблица переходов искомого конечного ав-
томата Мура А.
6. В случае необходимости найденный автомат Мура А интерпретируется как
автомат Мили В. Таблица переходов автомата А при этом принимается за таблицу
переходов В. Таблица выходов автомата В получается в результате подстановки в его
таблицу переходов вместо символов состояний символов, соответствующих состоя-
ниям выходных сигналов (отметок) автомата А.
Построенные автоматы А и В представляют заданные события множествами
своих состояний и (с точностью до пустого слова) множествами своих выходных сиг-
налов.
Событие, заданное регулярным выражением R, представляется множеством
всех тех и только тех состояний, которые отмечены множествами, содержащими в ка-
честве своих элементов выражение R
i
. Это же событие (за вычетом лишь пустого сло-
ва, если оно содержится в событии) представляется в автоматах А и В множеством
всех тех и только тех выходных сигналов (множеств), состоящих из выражений
R
1
,…,R
p
,
которые содержат в своем составе выражение R
i
(i = 1,..., p). Множество со-

Страницы