Шаг 3. Нахождение совместимых состояний автомата Мура

Состояния автомата Мура являются 0–совместимыми, если, не считая неопределённых отметок, они отмечены одинаковыми выходными сигналами. Состояния являются i– совместимыми для любого i= 1;2;... , если они 0–совместимы и автомат, переходя из них, перерабатывает допустимые слова длиной iодинаково. Процедура расщепления классов обязательно закончится за ограниченное количество шагов и, следовательно, более нерасщепляющиеся классы образуют конечные классы совместимых состояний.

После нахождения совместимых состояний автомата строится минимизированный нормализованный автомат Мура.

При табличном описании нормализованного автомата Мура, имеющего Nnклассов совместимых состояний, переход δ(Ni, zj)считается неопределённым, если для всех ai∈ Niпереходы δ(ai, zj)неопределённы. Если хотя бы для одного ai∈ Niпереход δ(ai, zj)определён, то в таблице нормализованного автомата указывается именно этот класс Nk, в который происходит переход. У частичного автомата таких переходов возможно несколько. Каждое класс Niотмечается выходным сигналом, который соответствует всем состояниям этого класса.

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

Более подробно рассмотрим применение методики минимизации абстрактных автоматов Мура на примере полностью определённого автомата S16(табл. 39). Автомат имеет четыре выходных сигнала, поэтому его состояния распределяются на четыре класса нулевой совместимости. Абстрактный автомат Мура S16– полностью определённый, как по выходам, так и по переходам, поэтому сразу находятся конечные классы совместимых состояний.

Дата добавления: 2015-07-26; просмотров: 218; Нарушение авторских прав

Мы поможем в написании ваших работ!