5.4. Построение автомата методом детерминизации

Из определения отношения непосредственно следует, что две последовательности множества Р тогда и только тогда находятся в отношении когда Следовательно, если в одно множество включать только те последовательности множества Р, для каждой пары которых, имеет место то множество разобьется на конечное число подмножеств (классов), которые будем обозначать

5.4.1. Пример построения автомата

Пусть Для этого множества будем иметь классы

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

Эта процедура соответствует замене состояния недетерминированного автомата двумя состояниями в результате чего он превращается в детерминированный автомат М.

В общем случае под детермнншзацмен будем понимать итеративную процедуру (более детально эта процедура будет рассмотрена чуть позднее построения автомата по автомату

Рис. 5.3. Граф переходов автомата

с помощью разбиения некоторых классов соответствующих состояниям автомата на непересекающиеся подклассы соответствующие состояниям автомата Разобьем класс автомата на подклассы по следующему принципу: любые две последовательности будем помещать в один и тот же подкласс, если для них имеет место для всех действий с.

Класс в этом случае можно разбить на два подкласса так как

Введем новые обозначения классов

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

Настоящим примером был проиллюстрирован подход к процедуре детерминизации. Перейдем к более строгой формулировке этой процедуры в виде алгоритма. Рассмотрим отношение на множестве если для всех а длиной Из определения отношения следует, что отношение как раз разбивает множество последовательностей Р из рассмотренного примера на классы Действительно отношение проверяется только для последовательностей о, длина которых равна такая последовательность существует только одна — пустая последовательность е. Тогда по определению для любых двух последовательностей имеет место если В то же время если выбрано равным или большим длине 11 самой длинной входной последовательности из множества Р, то из определения отношения следует, что отношение Ем совпадает с отношением а отношение разбивает множество Р на классы, каждый из которых является подклассом отношения т.е. для каждого класса существует класс такой, что общем случае автомат строится аналогично автомату

М. Состояниям этого автомата соответствуют классы

Функцией переходов автомата является функция а функцией выходов

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

Создадим с использованием отношения алгоритм построения автомата реализующего заданное множество S последовательностей.

5.4.2. Алгоритм детерминизации по множеству последовательностей

Запишем этот алгоритм в виде

а) принять

б) разбить множество Р на классы по отношению где является классом, содержащим пустую последовательность

в) отождествить классы с внутренними состояниями автомата Построить автомат с этими внутренними состояниями функцией переходов и функцией выходов

г) проверить, является ли автомат детерминированным. Если он детерминированный, то перейти к пункту е), в противном случае перейти к следующему пункту;

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

е) считать автомат автоматом Конец.

Рассмотренные алгоритмы построения автомата в качестве исходного задания использовали множество (язык) последовательностей 5. В то же время каждое такое множество однозначно представляется деревом, причем каждой последовательности однозначно соответствует состояние дерева из множества всех состояний В, в которое она ведет из начального состояния. Следовательно, эти алгоритмы могут быть модифицированы для работы сразу с деревом и его состояниями без перехода к множеству Для

этого достаточно заменить отношение на множестве следующим отношением: если для всех длиной Тогда функции переходов и выходов будут иметь вид

Следовательно, вместо алгоритма детерминизации по множеству последовательностей действий можно использовать следующий алгоритм.

5.4.3. Алгоретм детерминизации по множеству состояний

Запишем этот алгоритм в виде

а) принять

б) разбить множество В на классы по отношению где является классом, содержащим начальное состояние

в) отождествить классы с внутренними состояниями автомата Построить автомат с этими внутренними состояниями функцией переходов и функцией выходов

г) проверить, является ли автомат детерминированным. Если он детерминированный, то перейти к пункту е), в противном случае перейти к следующему пункту;

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

е) считать автомат автоматом М. Конец.