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

UptoLike

ВУЗ: 

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

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

Рубрика: 

55
тиях R
1
, ..., R
m
. Синтез конечного частичного автомата Мура или Мили, представ-
ляющего события R
1
, ..., R
m
, производится с учетом введенной области запрета. При
этом можно применять любой из описанных алгоритмов синтеза. Выходные сигналы
в синтезированных автоматах будут совпадать с буквами y
1
, ..., y
m
выходного алфави-
та отображения ψ , а автоматы будут индуцировать частичное отображение ψ
1
, про-
должающее исходное частичное отображение ψ с сохранением входного и выходного
алфавитов отображения ψ.
По второму варианту синтеза с исключением одного из событий исключается
из заданного множества y
1
, ..., y
m
регулярных выражений одно регулярное выражение
(обычно наиболее сложное). Пусть этим выражением будет y
1
. К оставшимся выра-
жениям y
2
, ..., y
m
применяется любой из алгоритмов синтеза частичных автоматов
Мили или Мура. При этом запрещенными считаются все те слова, у которых хотя бы
один непустой начальный отрезок (включая само слово) содержится одновременно в
нескольких (более чем в одном) событиях R
2
, ..., R
m
. Выходные сигналы, содержащие
более одного символа y
2
, ..., y
m
будут при этом неопределенными. Из оставшихся вы-
ходных сигналов y
2
, ..., y
m
, ( ) пустой выходной сигнал ( ) заменяется выходным сиг-
налом y
1
. После этого синтезированные автоматы будут индуцировать частичное ото-
бражение ψ
2
, продолжающее исходное частичное отображение ψ с сохранением его
входного и выходного алфавитов.
Второй вариант применяется с учетом следующих особенностей. Этот вариант
позволяет относительно просто произвести в таблице выходов автомата (обычной или
сдвинутой) дифференциацию пустых выходных сигналов, отождествляя только неко-
торую часть из них с выходным сигналом y
1
и производя замену остальных таких
сигналов черточками. Так, например, можно отождествить все слова исключаемого
события S(y
1
), совпадающие с начальными отрезками слов остающихся событий
S(y
2
), ..., S(y
m
).
Очевидно, что в этом случае пустые выходные сигналы, относящиеся к пусто-
му состоянию автомата, не будут представлять слов события S(y
1
), и их можно счи-
тать неопределенными. Неопределенным будет и пустое состояние.
Описанное уточнение второго варианта сводится к тому, что исключаемое со-
бытие S(y
1
) расширяется лишь до некоторой части дополнения объединения осталь-
ных событий.
3.5.2. Синтез автомата Мили
Применение общего метода решения задачи рассмотрим на примере синтеза
автомата Мили по индуцируемым им отображениям.
Пример. Построить автомат Мили, который преобразовывал бы числа от 1 до 9
в четверичной системе счисления, подаваемые последовательно на его вход, начиная
со старшего разряда, в приближенные (целочисленные) значения квадратного корня
из этих чисел, выдаваемые соответственно на выход также в четверичной системе
счисления, начиная со старшего разряда.
Решение. Приближенные значения квадратного корня из чисел от 1 до 9 будут
равны соответственно 1, 1, 2, 2, 2, 2, 3, 3, 3. Полученные числа в четверичной системе
счисления представим таблицей соответствия отображения ϕ, которое требуется реа-
лизовать автоматом:

Страницы