нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
 Скачать 0.65 Mb.
|
2.3. Процедура минимизации конечных автоматовПроцедура минимизация основана на рассмотрении отношений эквивалентности между упорядоченными парами состояний конечного автомата. Рассмотрим таблицу состояний автомата. Таблица 8
Таблица состояний автомата, подлежащего минимизации. Начнем с нахождения отношений и . В соответствии с функцией , находим первое разбиение . (1) Оно разбивает состояния автомата на два класса эквивалентности и (здесь вместо пишется 1, вместо пишется 2 и т.д.). Так как отношение рефлексивно и симметрично, то его всегда можно восстановить по множеству тех пар , для которых выполняется условие , Обозначим это множество через . В общем случае обозначим через множество упорядоченных пар , со свойствами . Для разбиения имеем: ={(1,3), (1,5), (1,7), (1,8), (3,5), (3,7), (3,8), (5,7), (5,8), (7,8,), (2,4), (2,6), (2,9), (4,6), (4,9), (6,9)}, ={(1,2), (1,4), (1,6), (1,9), (2,3), (3,4), (3,6), (3,9), (2,5), (4,5), (5,6), (5,9), (2,7), (4,7), (6,7), (7,9), (2,8), (4,8), (6,8), (8,9)}. Здесь и – классы эквивалентности относительно отношения . Следовательно, справедливы утверждения: , , а также , и т.д. Множество состоит из элементов множества и ещё пар (2,9), (4,9) и (6,9). Это связано, например, с тем, что входной символ a3, в соответствии с функцией , переводит упорядоченную пару состояний (2,9) в (4,7), а эта последняя пара принадлежит . Следовательно, пару (2,9) необходимо удалить из и добавить в . Добавление всех вышеуказанных пар к , определяет новое разбиение на классы эквивалентности: (2) Определим теперь множество . Оно состоит из элементов множества и ещё двух пар (2,6) и (4,6). Например, переводит (2,6) в (4,9), а эта последняя пара принадлежит . Поэтому разбиении имеем следующие классы эквивалентности: (3) Дальнейший перебор показывает, что , и, следовательно, . Конструкция покрывающего автомата получается следующей. Каждый класс эквивалентности последнего разбиения становится состоянием нового автомата. Например, обозначается через , через и т.д. Получается автомат с 5-ю состояниями, покрывающий первоначальный автомат с 9-ю состояниями. Так как выходы для каждого начального состояния в фиксированном классе эквивалентности не зависит от этого состояния при односимвольных входах, то в таблице состояний нового автомата выход прямо считывается с таблицы состояний первоначального автомата. Чтобы построить функцию перехода в следующее состояние, выберем по одному состоянию в каждом классе , и если элемент переводит в некоторое состояние из , то положим . Заметим, что это предписание однозначно: все переходят в состояния из после считывания . Результат этой процедуры, примененной к автомату с табл. 8, показан на табл. 9. Получен минимальный автомат. Таблица 9
Минимальный автомат, покрывающий автомат с табл. 9. Практически необязательно перечислять все пары из и . Достаточно на каждом шаге смотреть, переводит ли некоторый входной символ пару в разные классы эквивалентности и . Если да, то на следующем шаге состояния и следует разнести по разным классам. Пример. Рассмотрим автомат с пятью состояниями: Таблица 10
По выходной функции определяем, что: . Это приводит к разбиению . В соответствии с функцией входной символ 1 переводит состояние в , т.е. , кроме того, . Однако , так что (ибо и ). Следующее разбиение π2состоит из классов эквивалентности . Дальнейшего измельчения не происходит, ибо переводит каждый элемент класса эквивалентности в один и тот же класс. Итак, состояния и можно склеить в одно состояние , а состояния и – в состояние . Состояние получает новое обозначение . Новый минимальный автомат, покрывающий исходный автомат: Таблица 11
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||