Теория автоматов Определение автомата и его разновидности. Таблицы и графы переходов и выходов. Подавтоматы. Теорема о приведенном автомате Операции с автоматами Преобразование автомата Мили в автомат Мура и автомата Мура в автомат Мили

Эквивалентность автоматов.

Так как модель автомата представляет трехосновную алгебру, то для сравнения двух автоматов необходимо найти три оператора, формирующих отображение множеств X, Q и Y модели одного автомата на соответствующие множества модели другого автомата. После этого необходимо оценить влияние этих операторов на исполнение функций переходов и выходов каждым автоматом. Если на одинаковые последовательности входных символов автоматы генерируют одинаковые последовательности выходных символов, то такие автоматы эквивалентны.

Рассмотрим модели двух абстрактных автоматов:

(1.23)

Пусть даны операторы:

(1.24)

Если при исполнении функций переходов и выходов выполняются условия:

(1.25)

то совокупность операторов (f;g;h)формирует гомоморфное отображение модели автомата М₁ на модель автомата М₂ когда каждому значению x_1kX₁ y_1jY_ и q_1iQ₁ соответствуют единственные образы x_2kX₂y_2jY₂q_2iQ₁.

Пусть даны операторы:

(1.26)

Если при исполнении функций переходов и выходов выполняются условия:

(1.27)

то совокупность операторов ^-1f^-1;g^-1;h^-1 определяет гомоморфное отображение модели автомата М₂ на модель автомата М₁ когда каждому значению x_2kX₂ y_2jY и q_2iQ₂ соответствуют единственные образы x_1kX₁ y_1jY₁ q_1iQ₁ .

Если найдена совокупность операторов (^-1), для которой

_^-1= ^-1_ =1, (1.28)

то такое взаимное отображение называют изоморфным.

Изоморфное отображение рефлексивно, симметрично и транзитивно. Особый интерес для оценки эквивалентности автоматов представляет случай, когда f=1. По условиям (1.25) и (1.27) для x_kX имеем:

(1.29)

Если существуют такие q_1i и q_2i, для которых значения функций выходов ₁(q_1i;x_k) и ₂₍q_2i;x_k) совпадают для всех x_kX, то есть

₁(q_1i;x_k)=₂(q_2i;x_k), (1.30)

то g=g^-1=1, h(q_1i)=q_2i, h^-1(q_2i)=q_1i. При этом Y₁=Y₂=Y. Такие состояния q_1i и q_2i называют неотличимыми по выходам автоматов.

В результате просмотра множества пар неотличимых состояний (q_1i;q_2i)(Q₁Q₂) можно найти несколько подмножеств, которые формируют разбиение множества (Q₁Q₂) на классы неотличимых по выходу состояний.

Если для пары неотличимых состояний (q_1i;q_2i) значения функций переходов формируют для всех символов x_kX также пары неотличимых состояний ((q_1i[];x_k[]);(q_2i[];x_k[])), то состояния q_1i и q_2i называют совместимыми. В результате такого просмотра всех пар одного класса неотличимых состояний формируется его разбиение на классы совместимых состояний.

Состояния q_1i и q_2i являются эквивалентными, если для всякой входной последовательности =(x₁x₂...x_n) выполняется условие:

М₁(q_1i;)=М₂(q_2i;), (1.31)

Поэтому необходимо проследить изменения значений функций переходов ((q_1i[];x_k[]);(q_2i[];x_k[])) для каждого символа входной последовательности =(x₁x₂...x_n).

Множество всех пар (q_1i;q_2i), для которых выполняется условие (1.31), формирует класс эквивалентных состояний.

Если входной и выходной алфавиты у двух автоматов совпадают, то автомат M₂ покрывает автомат M₁, если ₂(h(q_1i);)=₁(q_1i;) для всех Xⁿ, а автомат M₁ покрывает автомат M₂, если входной и выходной алфавиты у этих автоматов общие и

По условиям изоморфизма автоматы M₁ и M₂ эквивалентны, если M₁ покрывает M₂ и M₂ покрывает M₁. У эквивалентных автоматов существуют эквивалентные состояния q_1i и q_2i.

Если для эквивалентных автоматов М₁ и М₂ имеем Q₁  Q₂, то автомат М₁, имеющий меньшее число состояний m₁ = Q₁, покрывает автомат М₂, имеющий большее число состояний m₂ = Q₂. Автомат, который нельзя покрыть автоматом с меньшим числом состояний, называют минимальным.

Для поиска эквивалентных состояний q_1i и q_2i удобно использовать таблицы переходов пар состояний двух автоматов. В каждой паре левый элемент есть состояние автомата М₁, а правый элемент - состояние автомата М₂. Левый столбец такой таблицы предназначен для указания неотличимых пар состояний, которые формируются по таблицам выходов автоматов следующим правилом:

"если среди множества состояний двух автоматов Q₁ и Q₂ найдется такая пара (q₁;q₂), у которой значения функций выходов равны для каждого символа входного алфавита x_kX, т.е. ₁(q_1i;x_k)=₂(q_2i;x_k), то состояния q₁ и q₂ неотличимы;"

Позициями таблицы являются пары состояний двух автоматов, в которые они переходят из соответствующих состояний пары неотличимых состояний при подаче на входы автоматов символа x_k. Значения очередных состояний могут быть найдены по таблицам переходов автоматов М₁ и М₂ для соответствующего символа x_kX, т.е. (q₁=(q_1i;x_k); q₂ = (q_2i;x_k)).

Пусть таблица переходов пар состояний двух автоматов представлена таблицей 1.19, где пары неотличимых состояний, приведенные в левом столбце, есть (q_1i;q_2j), (q_1j;q_2p), (q_1p;q_2s), (q_s;q_2i).

1) состояния q_1i и q_2j совместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М₁ и М₂ переходят в в пары также неотличимых состояний;

2) состояния q_1p и q_2s совместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М₁ и М₂ остаются в одной паре неотличимых состояний;

3) состояния q_1j и q_2p несовместимы, т.к. при приеме символа x₂ неотличимые состояния автоматов М₁ и М₂ переходят в различные пары неотличимых состояний;

4) состояния q_1s и q_2i несовместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М₁ и М₂ переходят в различные пары неотличимых состояний.

Следовательно, автоматы М₁ и М₂, даже при наличии совместимых состояний, не эквивалентны между собой.

Граф автомата М₁ приведен на рис.1.13, автомата М₂ - на рис.1.14. Определить эквивалентность автоматов М₁ и М₂.

Рис.1.13 Граф автомата М₁ Рис.1.14 Граф автомата М₂

Для автоматов М₁ и М₂ неотличимыми по выходу являются пары состояний (q₁₁;q₂₁), (q₁₂;q₂₂) и (q₁₃;q₂₁). При этом формируются два класса неотличимых состояний {(q₁₁;q₂₁);(q_13;q₂₁)} и {(q₁₂;q₂₂)}.

Если для неотличимой пары (q₁₁;q₂₁) при входном символе "0" автоматы М₁ и М₂ переходят в неотличимую пару состояний (q₁₃;q₂₁), а при входном символе "1" - в неотличимую пару (q₁₂;q₂₂), то состояние q₁₁ автомата М₁ и состояние q₂₁ автомата М₂ являются совместимыми.

Если для неотличимой пары состояний (q₁₂;q₂₂) при входном символе "0" автоматы М₁ и М₂ переходят в неотличимую пару состояний (q₁₁;q₂₁), а при входном символе "1" - в неотличимую пару (q₁₃;q₂₁), то состояние q₁₂ автомата М₁ и состояние q₂₂ автомата М₂ также являются совместимыми.

И наконец, если для неотличимой пары состояний (q₁₃;q₂₁) при входном символе "0" автоматы М₁ и М₂ переходят в неотличимую пару состояний (q₁₁;q₂₁), а при входном символе "1" - в неотличимую пару (q₁₂;q₂₂), то состояние q₁₃ автомата М₁ и состояние q₂₁ автомата М₂ являются совместимыми.

Если состояние q₁₃ автомата М₁ совместимо с состоянием q₂₁ автомата М₂, а состояние q₂₁ автомата М₂ совместимо с состоянием q₁₁ автомата М₁, то согласно свойству транзитивности состояние q₁₁ автомата М₁ совместимо с состоянием q₁₃ автомата М₁.

Проверку эквивалентности автоматов можно выполнить, обрабатывая одинаковые последовательности символов каждым автоматом и анализируя последовательности символов на их выходах.

Пусть для автомата М1 имеем q₁₁=q₀ и  = (01010101). Тогда процесс обработки входного слова формирует следующие последовательности:

вход: 0[1] 1[2] 0[3] 1[4] 0[5] 1[6] 0[7] 1[8];

q: q₁₁[1] q₁₃[2] q₁₂[3] q₁₁[4] q₁₂[5] q₁₁[6] q₁₂[7] q₁₃[8] q₁₂[9];

выход: 0[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8],

то есть ₁ (01111111).

Пусть для автомата М₂ имеем q₂₁=q₀ и =(01010101). Тогда процесс обработки входного слова формирует следующие последовательности:

вход: 0[1] 1[2] 0[3] 1[4] 0[5] 1[6] 0[7] 1[8];

q: q₂₁[1] q₂₁[2] q₂₂[3] q₂₁[4] q₂₂[5] q₂₁[6] q₂₂[7] q₂₁[8] q₂₂[9];

выход: 0[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8],

то есть ₂ (01111111).

Итак, автоматы М₁ и М₂ эквивалентны. Так как автомат М₂ имеет меньшее число внутренних состояний, то он покрывает автомат М₁.

МИНИМИЗАЦИЯ АВТОМАТОВ

Минимальный автомат - это автомат, имеющий наименьшее возможное количество состояний и реализующий заданную функцию выходов.

Два состояния автомата называются 1-эквивалентными, если, находясь в любом из этих состояний, автомат на один и тот же входной сигнал (входное слово длиной в 1) выдает один и тот же выходной сигнал. Два состояния автомата называются К- эквивалентными, если, начиная с любого из этих состояний, автомат на любые одинаковые слова длины К выдает одинаковые выходные слова (также длины К). Если два состояния К- эквивалентны для любых К, то их называют (просто) эквивалентными. Множество попарно эквивалентных состояний образует класс эквивалентности.

Смысл минимизации состоит в выявлении классов эквивалентности и замене каждого класса одним состоянием. Процедура минимизации состоит в следующем:

1. По таблице выходов автомата Мили (или по первой строке отмеченной таблице переходов автомата Мура) находятся состояния, имеющие одинаковые столбцы (отмеченные одинаковыми выходными сигналами) – это 1-эквивалентные состояния.

2. Далее используется таблица переходов. Все состояния, входящие в 1-эквивалентный класс, которые под воздействием первого сигнала перешли в состояния, принадлежащие в свою очередь 1-эквивалентному классу, образуют 2-эквивалентный касс.

3. Процедура разбиения на классы эквивалентности продолжается до тех пор, пока при очередном шаге К- эквивалентные классы не совпадут с (К-1)-эквивалентными, т.е. получатся эквивалентные классы.

4. Все состояния, входящие в один класс эквивалентности, заменяются одним состоянием.

	1	2	3	4	5	6
X1	Y1	Y1	Y1	Y1	Y1	Y2
X2	Y2	Y2	Y2	Y2	Y2	Y2

1 – эквивалентные классы определяются из табл. 8 , 2 – эквивалентные из табл. 9 , а 3 – эквивалентные и просто эквивалентные из табл. 10 .

РАСПОЗНАЮЩИЕ АВТОМАТЫ

Распознающий автомат – это автомат Мура, в котором фиксируется начальное состояние и подмножество состояний F⊂Q, называемое множеством заключительных состояний. Говорят, что автомат допускает (принимает, распознает, представляет) данное слово, если реакцией на это слово может быть переход автомата в одно из заключительных состояний.

Примеры. 1. Автомат (рис. 4) с начальным состоянием 1 и заключительным F1 и F2 допускает слова, в которых имеются только парные вхождения букв a и b, например,

a a, a a a a a a, b b a a и т.д.

Для распознавания часто используются частичные автоматы (рис.5), допускающие тоже множество слов, что и автомат, показанный на рис.4.

Здесь начальное состояние 1, а заключительное F. Слово считается недопустимым, если в результате реакции на него автомат не остановится в заключительном состоянии или если будет подан запрещенный (для данного состояния) входной сигнал. Например, воздействие входного слова ab на автомат вызовет переход в состояние 2 по букве a , но в этом состоянии не определен переход по букве b , следовательно, слово ab недопустимо. Если считать пустое (не содержащее ни одной буквы) слово допустимым, то можно еще более упростить частичный автомат, объединив начальное и заключительное состояния (рис.6).

3.Одним из наиболее широко используемых на практике типов распознающих автоматов является частичный недетерминированный автомат. Недетерминизм проявляется в том, что из одного состояния по одному и тому же входному сигналу возможны переходы в различные состояния, т.е. функция переходов заменяется отношением переходов. Недетерминированный автомат (рис.7) принимает, например, слова ab, aa, bb, bba и т.д. здесь начальное состояние A, а заключительное -F.

Таблица переходов данного автомата будет иметь вид табл.13.

A → aB A:: = aB / bB / aC

A → bb B:: = bC / b

A → aC C:: = a

B → bC

B → b

Такого рода грамматики называют регулярными, или автоматными.