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

UptoLike

ВУЗ: 

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

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

Рубрика: 

35
множество Y
1
на множество Y
2
; γ – отображающее множество Q
1
на множество Q
2
;
и, если удовлетворяются условия:
γ(q
1
) = q
2
;
γ(δ
1
(q
1
, x)) = δ
2
(γ(q),α(x));
β(λ
1
(q,x) = λ
2
(γ(q), α(x)) (для любых q∈Q
1
и х∈Х
1
),
то абстрактные автоматы А
1
и А
2
называются изоморфными. В этом случае говорят,
что отображения α, β и γ осуществляют изоморфное отображение одного автомата
на другой.
Изоморфные между собой абстрактные автоматы отличаются друг от друга
лишь обозначениями входных и выходных сигналов и состояний. Поэтому, в абст-
рактной теории автоматов, не занимаются проблемами кодирования состояний, а
также входных и выходных сигналов, изоморфные автоматы считаются одинаковыми
и будут заменяться один другим без каких-либо дальнейших пояснений. Операция
перехода от данного абстрактного автомата к изоморфному ему автомату состоит
просто в переобозначении элементов входного алфавита, выходного алфавита и
множества состояний автомата.
Способ сведения автоматов второго рода к автоматам первого рода, рассмот-
ренный ранее, мы условимся называть интерпретацией автомата второго рода как
автомата первого рода. Обратная интерпретация автомата первого рода как автомата
второго рода при сохранении того же самого множества состояний оказывается, во-
обще говоря, невозможной.
Произвольные автоматы первого рода, как отмечено ранее, называются авто-
матами Мили, а частный случай автоматов второго рода, у которых сдвинутая
функция выходов λ(q, x) не зависит от второй переменной х – автоматами Мура.
Способы задания автоматов были рассмотрены ранее в п. 1.5.3. Здесь отметим
одну из особенностей задания автоматов. Так, если произвольным образом заполнен-
ная таблица переходов или таблица выходов представляют собой таблицу переходов
или соответствующую таблицу выходов некоторого абстрактного автомата, то не вся-
кий граф и не всякая автоматная матрица могут служить графом или матрицей пере-
ходов некоторого автомата. Для того, чтобы это имело место, необходимо соблюде-
ние некоторых условий, связанных со свойствами функций переходов автомата.
Первое условие связано с однозначностью функций переходов и выходов и на-
зывается – условием однозначности.
Соблюдение этого условия требует, чтобы на графе автомата из любой верши-
ны выходило бы не более одной стрелки, обозначенной конкретным входным сигна-
лом.
Применительно к матрице это условие означает, что в любой ее строке кон-
кретный входной сигнал должен встречаться не более одного раза.
Второе условие, называется условием определенности, требующим, чтобы
для любого входного сигнала х из каждой вершины обязательно выходила бы стрел-
ка, обозначенная этим входным сигналом, и чтобы этот входной сигнал обязательно
присутствовал в каждой строке автоматной матрицы.
Частичным автоматом называется абстрактный автомат, у которого функ-
ция переходов или функция выходов (обычная или сдвинутая), или обе эти функции
определены не для всех пар значений своих аргументов q и х. В отличие от частич-
ных, ранее рассмотренные автоматы назывались вполне определенными.

Страницы