27. Эквивалентные состояния, эквивалентные автоматы, минимизация автоматов, алгоритм Мили.

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

• Два автомата S1 и S2 с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любоевходное слово совпадают. Другими словами, при подаче на вход эквивалентных автоматов, находящихся в одинаковом состоянии одних и тех же слов, их выходные слова также должны быть одинаковыми.

• Два автомата называются эквивалентными, если они имеют одинаковые входные и выходные алфавиты, и на одинаковые входные слова выдают одинаковые выходные слова (одинаковой длины).

• Два состояния называются 1-эквивалентными, если они не различимы с помощью одного входного сигнала (символа).

• Состояния называются k-эквивалентными, если начиная с них неразличимы входные слова длиной в k.

• Если состояния k-эквивалентны для любого k, то они эквивалентны.

Минимизация:

Задача минимизации - упростить автомат, то есть построить автомат, распознающий данный язык и имеющий минимально возможное количество состояний.

Конечный автомат может содержать лишние состояния двух типов: недостижимые и эквивалентные состояния.

Состояние q называется недостижимым, если к нему нет пути из начального состояния автомата.

Конечный автомат, не содержащий недостижимых и эквивалентных состояний, называется минимальным(приведенным).

Чтобы минимизировать КА, надо устранить недостижимые и объединить эквивалентные состояния.

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

Алгоритм Мили (проверка эквивалентности состояний)

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

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

3. Последовательно по строкам отыскиваются отличающиеся пары состояний,

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

4. Находятся невыделенные строки, в которых имеются пары, вычеркнутые в

первом столбце на предыдущем этапе. Если такие строки имеются, то для них

зачеркиваются пары в первом столбце. Такой процесс повторяется до тех пор,

пока на очередном этапе не обнаруживаются невыделенные строки, в которых

имеются пары, вычеркнутые в первом столбце на предыдущем этапе.

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

Корректность алгоритма:

Алгоритм выполняется за конечное число шагов, так как на каждом шаге в каждый левый столбец добавляется не менее одной новой пары состояний, а число пар конечно в силу конечности числа состояний.

Алгоритм определяет эквивалентность состояний s и t, так как в случае замкнутости таблицы все входящие символы сохраняют пары, стоящие в левом столбце, а значит, и подобие исходящих состояний, что гарантирует отсутствие различающей цепочки.

Замечания:

1. Алгоритм гарантирует выделение лишь одной пары эквивалентных состояний.

2. Если происходит проверка на эквивалентность состояний одного автомата, пары состояний из левого столбца можно считать неупорядоченными.

3. В противном случае пары упорядочены.