Что такое приведенный автомат
Перейти к содержимому

Что такое приведенный автомат

  • автор:

Минимизация конечных автоматов

Цель. Показать, что для каждого регулярного множества однозначно находится конечный автомат с минимальным числом состояний.

По данному конечному автомату М можно найти наименьший эквивалентный ему конечный автомат, исключив все недостижимые состояния и затем склеив лишнее состояние. Лишнее состояние определяется с помощью разбиения множества всех состояний на классы эквивалентности так, что каждый класс содержит неразличимые состояния и выбирается как можно шире. Потом из каждого класса берётся один представитель в качестве состояния сокращенного (или приведённого) автомата.

Таким образом можно сократить объём автомата М, если М содержит недостижимые состояния или два или более неразличимые состояния. Полученный автомат будет наименьший из конечных автоматов, распознающий регулярное множество, определяемое первоначальным автоматом М.

Определение.

Пусть М = (Q, q0, F) конечный автомат, а q1 и q2 два его различные состояния. Будем говорить, что цепочка х различает состояния q1 и q2, если (q1, х)? ? (q3, е), (q2, х)? ? (q4 ,е) и одно из состояний q3 и q4 принадлежит F. Будем говорить, что q1 и q2 k- неразличимы, и писать q1q2, если не существует такой цепочки х, различающей q1 и q2, у которой |x|k. Будем говорить, что состояния q1 и q2, неразличимы и писать q1?q2, если они k — неразличимы для любого k0.

Состояние qQ называется недостижимым, если не существует такой входной цепочки х, что (q0, х)? ? (q, е).

Автомат М называется приведенным, если в Q нет недостижимых состояний и нет двух неразличимых состояний.

Пример. Рассмотрим конечный автомат М с диаграммой (рис. 3.4).

Диаграмма автомата М

Рис. 3.4. Диаграмма автомата М

Чтобы сократить М, заметим сначала, что состояния F и G недостижимы из начального состояния А, так что их можно устранить. Пока качественно, а позже строго мы установим, что классами эквивалентности отношений являются A>, B, D> и C, E>. Тогда, взяв представителями этих множеств p, q и r, можно получить конечный автомат вида (рис. 3.5).

Приведенный конечный автомат

Рис. 3.5. Приведенный конечный автомат

Перед тем, как построить алгоритм канонического конечного автомата, введём лемму:

Пусть М = (Q, q0, F) конечный автомат с n состояниями. Состояния q1 и q2 неразличимы тогда и только тогда, когда они (n-2) — неразличимы, т.е. если два состояния можно различить, то их можно различить с помощью входной цепочки, длина которой меньше числа состояний автомата.

Алгоритм построения канонического конечного автомата.

Конечный автомат М = (Q, q0, F).

Эквивалентный конечный автомат М‘.

Шаг 1. Применив к диаграмме автомата ^ М алгоритм нахождения множества вершин, достижимых из данной вершины ориентированного графа, найти состояния достижимые из q0. Установить все недостижимые состояния.

Шаг 2. Строить отношения эквивалентности ? 0 , ? 1 по схеме:

Шаг 3. Построить конечный автомат

где Q‘ — множество классов эквивалентности отношений ? (обозначим через [p] класс эквивалентности отношений, содержащий состояние р);

(‘[p], а) = [q], если (р, а) = q;

Автомат М‘, построенный по данному алгоритму имеет наименьшее число состояний среди всех конечных автоматов, допускающих язык L(M).

Найдём приведённый конечный автомат автомату М (рис. 3.6).

Диаграмма автомата М

Рис. 3.6. Диаграмма автомата М

Отношения для к0 имеют следующие классы эквивалентности:

Так как ? 2 = ? 1 , то ? = ? 1 .Приведённый автомат М’ будет (a, b>, ‘, A, >), где ‘ определяется следующей таблицей.

Таблица 3.4 — Приведенный конечный автомат

Приведенные автоматы

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

Процесс приведения можно повторять до тех пор, пока не получится приведенный автомат. Таким образом, для каждого конечного автомата существует эквивалентный ему приведенный автомат. Приведенный автомат, полученный таким способом, имеет меньшее число состояний, чем исходный (если исходный не был уже приведенным), и может быть более компактно реализован на вычислительной машине.

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

Чтобы увидеть это на примере, рассмотрим два приведенных автомата (рис. 5.15, а-б). Применив процедуру из параграфа 5.5 к паре начальных состояний (А, 1), построим таблицу эквивалентности состояний (рис. 5.16).

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

Рис. 5.15. Приведенные автоматы, одинаковые с точностью до имен состояний

Проверка на эквивалентность состояний двух разных автоматов (рис. 5.15, а-б)

Рис. 5.16. Проверка на эквивалентность состояний двух разных автоматов (рис. 5.15, а-б)

Из таблицы эквивалентности состояний (рис. 5.16) видно, что следующие пары эквивалентны:

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

Таким образом, эти два автомата идентичны с точностью до имен состояний. Чтобы убедиться, что это справедливо для любой пары эквивалентных приведенных автоматов М и N, посмотрим, что происходит при применении к М и N метода проверки эквивалентности из параграфа 5.5.

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

Каждое состояние автомата М может входить в пару не более чем с одним состоянием автомата N, и, наоборот, так как если бы состояние т автомата М было эквивалентно двум состояниям щ и п2 автомата N, то состояния п и П2 были бы эквивалентны друг другу, что противоречит нашему предположению о том, что N — приведенный автомат.

Кроме того, каждое состояние т автомата М образует пару хотя бы с одним состоянием автомата N, и, наоборот, так как входная цепочка, которая переводит автомат М в состояние т, переведет также пару начальных состояний из таблицы эквивалентности в пару, содержащую состояние т. Отсюда заключаем, что каждое состояние автомата М эквивалентно в точности одному состоянию N и наоборот. Это означает, что автоматы М и N одинаковы во всем, кроме имен состояний.

Таким образом, если не придавать значения именам состояний, то для каждой проблемы распознавания можно найти только один приведенный автомат. Это означает, что, какой бы распознаватель ни был выбран для некоторой проблемы распознавания и каким бы образом ни происходило приведение его состояний, можно построить только один приведенный автомат. Этот автомат является минимальным автоматом, о существовании которого говорилось в начале параграфа 5.4.

§3.4. Приведённый автомат

Назовём состояния и автомата неотличимыми, если для всех Состояния и отличимы, если при некотором Положим если и неотличичимы.

Нетрудно видеть, что отношение неотличимости ~ на множестве состояний автомата является отношением эквивалентности. Это отношение вызывает разбиение множества на непересекающиеся классы эквивалентности: При этом любые два состояния лежащие в одном классе, неотличимы, а любые два состояния из разных классов отличимы.

Множество классов отношения ~ (фактор-множество обозначим через Построим новый автомат В качестве входного и выходного алфавитов автомата возьмём те же множества и которые были у автомата а в качестве множества состояний возьмём множество Надо определить теперь функции и

Пусть Наиболее естественным является следующее определение значения взять какой-нибудь элемент принадлежащий классу найти а затем класс, в котором лежит элемент объявить значением То есть считать, что

Докажем корректность этого определения, т.е.

независимость от выбора представителя в классе эквивалентности. Пусть Определение будет некорректным, если окажется, что Докажем, что определение корректно. Если то при некотором Это означает, что Следовательно, что противоречит условию. Итак, поэтому определение (1) корректно.

Функцию определим на по формуле

По определению неотличимости состояний мы имеем поэтому определение (2) корректно.

Автомат называется приведённым автоматом, соответствующим автомату

Докажем, что у приведённого автомата все состояния отличимы друг от друга. Пусть Тогда для всех Отсюда по формуле (2) получаем, что при всех Следовательно, Отсюда следует, что Итак, у автомата неотличимыми являются только совпадающие друг с другом состояния.

Автомат и приведённый автомат работают одинаково: для любой входной последовательности последовательность на выходе автомата и автомата одна и та же: и т.д. (здесь начальное состояние). Решение типовых задач

Пример 1. Построить приведённый автомат для автомата, заданного следующей диаграммой Мура, изображенной на рис. 3.14.

Решение. Вычислим: , , , , . Следовательно, состояние отличимо от всех остальных. Мы получаем (пока) следующее разбиение множества на классы, т.е. непересекающиеся подмножества: (далее это разбиение будет измельчаться).

Далее вычисляем: Отсюда следует, что не может лежать в одном классе с или с или и т.д.

Разбиение, полученное ранее, измельчается до следующего: Положим Покажем, что это окончательное разбиение. Имеем: поэтому Аналогично получаем и т.д., т.е. функция “не разбивает” классы. Следовательно, классы можно считать состояниями нового автомата. Это и есть приведённый автомат, его диаграмма Мура изображена на рисунке 3.15.

Пример 2. Построить приведённый автомат для автомата , заданного следующей таблицей 3.7:

Решение. Верхняя строка таблицы 11011 определяет разбиение нижняя строка — разбиение Их пересечение это разбиение Докажем, что состояния неотличимы друг от друга.

В столбцах таблицы, соответствующих этим состояниям, мы имеем: значит, функция на состояниях принимает одинаковые значения. Кроме того, другая часть столбцов: такова, что лежат в одном классе разбиения. Это доказывает, что неотличимы. Из таблицы автомата теперь нетрудно получить таблицу приведённого автомата для этого достаточно взять по одному представителю в каждом классе разбиения Таким образом, мы получаем таблицу 3.8:

Задачи для самостоятельного решения

1. Автомат задан диаграммой Мура. Построить диаграмму Мура приведённого автомата

2. Автомат задан таблицей. Построить таблицу приведённого автомата

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *