Теория автоматов. 5.Минимизация полностью определенных автоматов

Два состояния эквивалентны, если реакция автомата на любое входное слово будет одинаково. (a_m ~ a_s).

Два состояния К-эквивалентны, если реакция совпадает на любое слово длины К. (a_m ~k~ a_s)

Эквивалентность состояний используется при минимизации.

Состояния a_m и a_s являются эквивалентными, если λ(a_m, ξ) = λ(a_s, ξ) для всевозможных входных слов ξ.

Минимизация полностью определенных автоматов методом Ауфенкампа и Хона (метод последовательных разбиений):

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

Алгоритм:

1. Находим последовательные разбиения п1, п2, …, пк, пк+1 множества А на классы одно-, двух-, К-, К+1- эквивалентных состояний до тех пор, пока в каком-то (К+1) шаге не окажется, что пк = пк+1.

2. В каждом классе эквивалентности разбиения п выбирается по одному состоянию, в результате чего получаем множество А’ состояний минимального автомата S’ = {A’,z,w,?’,?’,a1’} эквивалентному автомату S.

3. Для определения функции переходов и выходов автомата S’ в таблице переходов и выходов вычеркиваются столбцы, соответствующие не вошедшим в А’ состояниям. В оставшихся столбцах не вошедшие в множество А состояния заменяются на эквивалентные.

4. В качестве начального состояния а1’ выбирается состояние из множества А’, эквивалентное состоянию а1. В частности, удобно за а1’ принимать само состояние а1.

Алгоритм минимизации автомата Мили с помощью таблицы пар состояний:

1. Находят одноэквивалентные разбиения состояний автомата

2. Строим таблицу пар. Строки таблицы пар помечены парами одноэквивалентных состояний, столбцы – входными сигналами. На пересечении строк и столбцов в таблице пар записываются пары состояний, которые являются первоприемниками по отношению к конкретному входному сигналу.

3. Последовательно по строкам отыскиваются отличающиеся пары состояний, которые отсутствуют в первом основном столбце таблицы пар. Если в какой-либо строке имеется хотя бы одна такая пара, то в этой строке зачеркивается пара в первом столбце. Такие строки, в которых зачеркнуты пары в первом столбце, называются выделенными строками.

4. Находятся невыделенные строки, в которых имеются пары, вычеркнутые в первом столбце на предыдущем этапе. Если такие строки имеются, то для них зачеркиваются пары в первом столбце. Такой процесс повторяется до тех пор, пока на очередном этапе не обнаруживаются невыделенные строки, в которых имеются пары, вычеркнутые в первом столбце на предыдущем этапе.

5. Оставшиеся незачеркнутые пары в первом столбце таблицы образуют все пары эквивалентных состояний.