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

UptoLike

ВУЗ: 

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

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

Рубрика: 

37
Выбирая в качестве выходного алфавита автомата
U выходной алфавит ото-
бражения ϕ, построим сдвинутую функцию выходов λ(а) автомата Мура
U следую-
щим образом: для любого непустого слова а
i
из А полагаем λ(а
i
) равным последней
букве слова ϕ(а
i
); на пустом слове функция λ(a) остается неопределенной.
В качестве начального состояния автомата выбираем пустое слово ε и получа-
ем автомат Мура, индуцирующий исходное отображение ϕ. В самом деле, пусть,
q = x
i1
, x
i2
,
…, x
ik
– любое допустимое слово отображения ϕ. Тогда все его начальные
отрезки будут также допустимыми словами (в силу условия 2). После подачи на вход
построенного автомата слова q, будет осуществляться последовательный его перевод
в состояние ε x
i1
= x
i1
, x
i2
,…, x
ik
.
При этом автомат выдает некоторую последовательность выходных букв
y
j1
, y
j2
,
…, y
jk
= p. Из способа определения данного автомата следует, что последняя
буква слова р совпадает с последней буквой слова ϕ(q), предпоследняя буква
слова р – с последней буквой слова ϕ(x
i1
, x
i2
, …, x
ik-1
), которая в силу условия 4,
совпадает с предпоследней буквой слова ϕ(q) и т. д. Продолжая сравнение и исполь-
зуя условия 3, можно установить совпадение всех букв слова р с соответствующими
им буквами слова ϕ(q). Следовательно, построенный автомат Мура U индуцирует ис-
ходное (частичное) отображение ϕ.
Поскольку можно интерпретировать автомат Мура U
как автомат Мили, то
очевидно следующее предложение.
Если алфавитное отображение ϕ удовлетворяет сформулированным выше че-
тырем условиям автоматности, то можно построить автоматы Мили и Мура (как пра-
вило, бесконечные), индуцирующие это отображение. В случае, когда область опре-
деления отображение ϕ конечна, эти автоматы также можно считать конечными.
Данное предложение позволяет применять термины «автоматное отображе-
ние» по всему алфавитному отображению, удовлетворяющему условиям автоматности.
Из этого предложения вытекает конструктивный прием, позволяющий по лю-
бому автоматному отображению с конечной областью определения (заданному на
конечном множестве слов) строить индуцирующий это отображение конечный авто-
мат Мили или Мура.
Ранее рассматривалась возможность интерпретации автомата Мура как авто-
мат Мили с тем же самым числом состояний. Рассмотрим теорему:
Для всякого конечного автомата Мили существует эквивалентный ему (инду-
цирующий то же самое отображение) конечный автомат Мура. Существует еди-
ный конструктивный прием (универсальный алгоритм преобразования автоматов
Мили в автоматы Мура), позволяющий по произвольному конечному автомату Мили,
имеющему m входных сигналов и n состояний, построить эквивалентный ему авто-
мат Мура, имеющий не более m
⋅
n + 1 состояний.
Условия автоматности накладывают весьма жесткие ограничения на класс ото-
бражений, которые могут быть индуцированы абстрактными автоматами. Большин-
ство алфавитных отображений, с которыми приходится иметь дело на практике, в ча-
стности большинство алгоритмов, не удовлетворяют этим условиям. Существует, од-
нако, стандартный прием, позволяющий индуцировать любое алфавитное отображе-
ние в автоматное.
Рассмотрим этот прием.

Страницы