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