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

UptoLike

ВУЗ: 

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

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

Рубрика: 

48
ставлены множеством выходных сигналов. Продемонстрируем работу усовершенст-
вованных алгоритмов синтеза на примере.
Пример. Найти конечные автоматы Мура и Мили, представляющие регуляр-
ные события в алфавите (х, у), заданные следующими регулярными выражениями:
R = x {y}, P = x x.
Выпишем нулевой комплекс К
0
заданных регулярных выражений:
R = | x | { y | }, P = | x | x |.
0 1 2 0 3 4
В этом комплексе места 1 и 3 являются соответственными между собой, места
1 и 2 – подобными, а место 4 – тупиковым.
Проведем последовательные отождествления мест в соответствии с правилом
2а. Отождествляя сначала соответственные места, придем к комплексу:
R = | x | { y | }, P = | x | x |.
0 1 2 0 1 4
После такого отождествления места 1 и 2 перестают быть подобными (за ме-
стом 1 х – следует место 4, а за местом 2 – нет). Дальнейшие отождествления по
правилу 2а невозможны.
Применяя теперь правило 3, получим размеченный комплекс:
R = | x | { y | } , P = | x | x |.
0 1 2 0 1 4
1 1
2 2
По правилам 4 и 5 получаем отмеченную таблицу 3.5 переходов автомата Мура.
После переобозначений:
0 → 1, 1 → 2, 2 → 3, 4 → 4, * → 5, (R) → u, (P) → v
1
, ( ) → w, получаем отме-
ченную таблицу 3.6 переходов автомата Мура. (Переобозначение производят с целью
упрощения записи таблиц переходов и выходов).
Таблица 3.5 Таблица 3.6
( ) (R) (R) (P) ( ) w u u v w
0 1 2 4 * 1 2 3 4 5
x 1 4 * * * x 2 4 5 5 5
y * 2 2 * * y 5 3 3 5 5
Событие R представлено в этом автомате выходным сигналом u, а событие Р –
выходным сигналом v. Применяя правило 6, получим таблицы переходов и выходов
автомата Мили (табл. 3.7 и 3.8).
Таблица 3.7 Таблица 3.8
0 1 2 4 5 1 2 3 4 5
x 2 4 5 5 5 x u v w w w
y 5 3 3 5 5 y w u u w w
При использовании основного и усовершенствованного алгоритмов синтеза
необходимо использовать правила 5б и 6а.

Страницы