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



жүктеу 0.49 Mb.
бет3/4
Дата12.06.2016
өлшемі0.49 Mb.
1   2   3   4

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


Эквивалентность автоматов определяют по их одинаковой реакции на входные последовательности символов, то есть по формированию одинаковых выходных последовательностей символов.

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

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

(1.23)

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

(1.24)

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

(1.25)

то совокупность операторов (f;g;h)формирует гомоморфное отображение модели автомата М1 на модель автомата М2 когда каждому значению x1kX1 y1jY и q1iQ1 соответствуют единственные образы x2kX2y2jY2q2iQ1.

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

(1.26)

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

(1.27)

то совокупность операторов -1f-1;g-1;h-1 определяет гомоморфное отображение модели автомата М2 на модель автомата М1 когда каждому значению x2kX2 y2jY и q2iQ2 соответствуют единственные образы x1kX1 y1jY1 q1iQ1 .

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

-1= -1 =1, (1.28)

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

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

(1.29)

Если существуют такие q1i и q2i, для которых значения функций выходов 1(q1i;xk) и 2(q2i;xk) совпадают для всех xkX, то есть

1(q1i;xk)=2(q2i;xk), (1.30)

то g=g-1=1, h(q1i)=q2i, h-1(q2i)=q1i. При этом Y1=Y2=Y. Такие состояния q1i и q2i называют неотличимыми по выходам автоматов.

В результате просмотра множества пар неотличимых состояний (q1i;q2i)(Q1Q2) можно найти несколько подмножеств, которые формируют разбиение множества (Q1Q2) на классы неотличимых по выходу состояний.

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

Состояния q1i и q2i являются эквивалентными, если для всякой входной последовательности =(x1x2...xn) выполняется условие:

М1(q1i;)=М2(q2i;), (1.31)

Поэтому необходимо проследить изменения значений функций переходов ((q1i[];xk[]);(q2i[];xk[])) для каждого символа входной последовательности =(x1x2...xn).

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

Если входной и выходной алфавиты у двух автоматов совпадают, то автомат M2 покрывает автомат M1, если 2(h(q1i);)=1(q1i;) для всех Xn, а автомат M1 покрывает автомат M2, если входной и выходной алфавиты у этих автоматов общие и


1(h-1(q2i);)=2(q2i;) для всех Xn.

По условиям изоморфизма автоматы M1 и M2 эквивалентны, если M1 покрывает M2 и M2 покрывает M1. У эквивалентных автоматов существуют эквивалентные состояния q1i и q2i.

Если для эквивалентных автоматов М1 и М2 имеем Q1  Q2, то автомат М1, имеющий меньшее число состояний m1 = Q1, покрывает автомат М2, имеющий большее число состояний m2 = Q2. Автомат, который нельзя покрыть автоматом с меньшим числом состояний, называют минимальным.

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

"если среди множества состояний двух автоматов Q1 и Q2 найдется такая пара (q1;q2), у которой значения функций выходов равны для каждого символа входного алфавита xkX, т.е. 1(q1i;xk)=2(q2i;xk), то состояния q1 и q2 неотличимы;"

Позициями таблицы являются пары состояний двух автоматов, в которые они переходят из соответствующих состояний пары неотличимых состояний при подаче на входы автоматов символа xk. Значения очередных состояний могут быть найдены по таблицам переходов автоматов М1 и М2 для соответствующего символа xkX, т.е. (q1=(q1i;xk); q2 = (q2i;xk)).

Пусть таблица переходов пар состояний двух автоматов представлена таблицей 1.19, где пары неотличимых состояний, приведенные в левом столбце, есть (q1i;q2j), (q1j;q2p), (q1p;q2s), (qs;q2i).


текущая пара неотличимых состояний (q1;q2)

символы входного алфавита xiX

x1

x2



xn











(q1i;q2j)

(q1i;q2j)

(q1j;q2p)



(q1s;q2i)

(q1j;q2p)

(q1i;q2j)

(q1p;q2p)



(q1s;q2i)

(q1p;q2s)

(q1j;q2p)

(q1j;q2p)



(q1j;q2p)

(q1s;q2i)

(q1s;q2p)

(q1p;q2j)



(q1j;q2i)











Анализ таблицы показывает, что

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

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

3) состояния q1j и q2p несовместимы, т.к. при приеме символа x2 неотличимые состояния автоматов М1 и М2 переходят в различные пары неотличимых состояний;

4) состояния q1s и q2i несовместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М1 и М2 переходят в различные пары неотличимых состояний.

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



Пример 1.5. Пусть даны автомат M1=X1;Y1;Q1;11,где X1{0;1}, Y1{0;1}, Q1={q11;q12;q13}, 1 и 1 (см. таблицу 1.20) и автомат M2=X2;Y2;Q2;22,гдеX2{0;1}, Y2{0;1}, Q2={q21;q22}, 2 и2 (см. таблицу 1.21).

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




текущее состояние qQ1

символы входного алфавита xX1




текущее состояние qQ2

символы входного алфавита xX2

0

1




0

1

q11

q13;0

q12;1




q21

q21;0

q22;1

q12

q11;1

q13;0




q22

q21;1

q21;0

q13

q11;0

q12;1













Рис.1.13 Граф автомата М1 Рис.1.14 Граф автомата М2

Для автоматов М1 и М2 неотличимыми по выходу являются пары состояний (q11;q21), (q12;q22) и (q13;q21). При этом формируются два класса неотличимых состояний {(q11;q21);(q13;q21)} и {(q12;q22)}.

Если для неотличимой пары (q11;q21) при входном символе "0" автоматы М1 и М2 переходят в неотличимую пару состояний (q13;q21), а при входном символе "1" - в неотличимую пару (q12;q22), то состояние q11 автомата М1 и состояние q21 автомата М2 являются совместимыми.

Если для неотличимой пары состояний (q12;q22) при входном символе "0" автоматы М1 и М2 переходят в неотличимую пару состояний (q11;q21), а при входном символе "1" - в неотличимую пару (q13;q21), то состояние q12 автомата М1 и состояние q22 автомата М2 также являются совместимыми.

И наконец, если для неотличимой пары состояний (q13;q21) при входном символе "0" автоматы М1 и М2 переходят в неотличимую пару состояний (q11;q21), а при входном символе "1" - в неотличимую пару (q12;q22), то состояние q13 автомата М1 и состояние q21 автомата М2 являются совместимыми.

Если состояние q13 автомата М1 совместимо с состоянием q21 автомата М2, а состояние q21 автомата М2 совместимо с состоянием q11 автомата М1, то согласно свойству транзитивности состояние q11 автомата М1 совместимо с состоянием q13 автомата М1.

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

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

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

q: q11[1] q13[2] q12[3] q11[4] q12[5] q11[6] q12[7] q13[8] q12[9];

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

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

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

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

q: q21[1] q21[2] q22[3] q21[4] q22[5] q21[6] q22[7] q21[8] q22[9];

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

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

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

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

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

Два состояния автомата называются 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

2

3

4

5

6

X1

1




4




6




2




6




4







α




α




β




α




β




α

X2

2




1




3




2




5




5







α




α




α




α




α




α


α

α

β

β

γ

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



Таблица 10




1

2

4

3

5

6

X1

1




4




2




6




6




4







α




α




α




γ




γ




α

X2

2




1




2




3




5




5







α




α




α




β




β




β

В качестве имен состояний минимального автомата возьмем имена классов. Минимальный автомат представлен табл. 11 и 12. Таблица 11 Таблица 12




α

β

γ







α

β

γ

X1

α

γ

α




X1

Y1

Y1

Y2

X2

α

β

β




X2

Y2

Y2

Y2

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

Распознающий автомат – это автомат Мура, в котором фиксируется начальное состояние и подмножество состояний 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

B

C

D

a

B,C




F




b

B

C,F







Пустые клеточки говорят о том, что автомат частичный, а наличие сразу нескольких букв в одной клеточке – о том, что автомат недетерминированный. Для таких автоматов обычно предпочитают использовать не табличное и не графовые представления, а запись в виде так называемых продукций или грамматических правил, представленных в двух столбцах соответственно:

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

A → bb B:: = bC / b

A → aC C:: = a

B → bC

B → b


C → a

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


1   2   3   4


©dereksiz.org 2016
әкімшілігінің қараңыз

    Басты бет