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

 

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

Определение Два различных состояния и в конечном автомате называются n-эквивалентными, nÎ NÈ {0}, если, находясь в одном их этих состояний и получив на вход любую цепочку символов w: wÎ T^*, |w|£ n, автомат может перейти в одно и то же множество конечных состояний.

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

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

В теории КА доказано, что каждое регулярное множество распознается единственным для данного множества ДКА с минимальным числом состояний. Рассмотрим алгоритмы построения минимального ДКА.

Устранение недостижимых состояний КА

 

Алгоритм Устранение недостижимых состояний КА

 

Вход: КА .

Выход: КА .

 

Шаг 1. Поместить начальное состояние КА в список достижимых состояний , т.е. .

Шаг 2. Для новых элементов списка достижимых состояний пополнить список группой их состояний-приемников, отсутствующих в списке, т.е. .

Шаг 3. Повторить шаг 2, пока список достижимых состояний не перестанет меняться. То есть, если , то i=i+1, иначе .

Шаг 4. Исключить из множества Q состояний КА все состояния, отсутствующие в списке Q_д достижимых состояний, т.е. .

Шаг 5. Исключить недостижимые заключительные состояния и функции переходов, содержащие недостижимые состояния, т.е. , .

 

Пример Устранить недостижимые состояния КА , где Q = {A, B, C, D, E, F, G}, T = {a, b}, H = {A}, Z = {D, E} и функция переходов задана таблицей 2.4. Граф исходного КА М представлен на рисунке 2.3.

 

Таблица 2.4 – Функция переходов конечного автомата M

 

F	A	B	C	D	E	F	G
a	B			C	B	D	F
b	C	D	E	E	D	G	E

 

Рисунок 2.2 – Граф исходного конечного автомата М

 

Последовательность устранения недостижимых состояний КА имеет вид:

 

Q₀ = {A};

Q₁ = {A, B, C};

Q₂ = {A, B, C, D, E};

Q₃ = {A, B, C, D, E}; т.к. Q₂ = Q₃, то Q_д = {A, B, C, D, E}.

Q_н = {F, G}; = {A, B, C, D, E}; = {D, E}.

Функция переходов автомата представлена в таблице 2.6.

 

Таблица 2.5 - Функция переходов автомата

 

F	A	B	C	D	E
a	B			C	B
b	C	D	E	E	D

 

b

Граф КА после устранения недостижимых состояний представлен на рисунке 2.5.

 

 

Рисунок 2.3 - Граф КА после устранения недостижимых состояний

 

Объединение эквивалентных состояний КА

Алгоритм Объединение эквивалентных состояний КА

 

Вход: КА без недостижимых состояний.

Выход: минимальный КА .

Шаг 1. На первом шаге строим нулевое разбиение R(0), состоящее из двух классов эквивалентности: заключительные состояния КА - Z и не заключительные - Q-Z.

Шаг 2. На очередном шаге построения разбиения R(n) в классы эквивалентности включить те состояния, которые по одинаковым входным символам переходят в n-1 эквивалентные состояния, т.е.

 

.

 

Шаг 3. До тех пор, пока R(n) ¹ R(n-1) полагаем n=n+1 и идем к шагу 2.

Шаг 4. Переобозначить оставшиеся неразбитые группы состояний и включить их в таблицу новых обозначений состояний автомата.

Шаг 5. Определить эквивалентный КА в новых обозначениях.

Пример Минимизировать конечный автомат из предыдущего примера.

Последовательность построения разбиений будет иметь вид:

 

R(0) = {{A, B, C}, {D, E}}, n = 0;

R(1) = {{A}, {B, C}, {D, E}}, n = 1;

R(2) = {{A}, {B, C}, {D, E}}, n=2.

Т.к. R(1) = R(2), то искомое разбиение построено.

 

Переобозначим оставшиеся неразбитые группы состояний:

X={B, C}, Y={D, E}.

Получим минимальный автомат , где ={A, X, Y}, ={Y}.

Функция переходов автомата представлена в таблице 2.7.

 

Таблица 2.6 - Функция переходов автомата

 

	A	X	Y
a	X		X
b	X	Y	Y

 

Граф переходов конечного автомата после его минимизации показан на рисунке 2.4.

 

 

 

Рисунок 2.4 – Граф минимального ДКА

 

2.4 Взаимосвязь способов определения грамматик

 

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

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. Возможные задержки и неисправности автомата при стрельбе, способы их устранения
2. Вопрос 6. НЕПОЛНАЯ РАЗБОРКА И СБОРКА АВТОМАТА
3. Вопрос 9. ВВП – центральный показатель СНС. Методы исчисления ВВП: производственный, распределительный, метод конечного использования.
4. Информационные инструменты бесконечного расширения
5. Круг № 3: «Актуально бесконечного не существует»
6. Метод конечного использования.
7. Минимизация логических функций
8. Минимизация логических функций
9. НАЗНАЧЕНИЕ, БОЕВЫЕ СВОЙСТВА И УСТРОЙСТВО АВТОМАТА КАЛАШНИКОВА
10. Оборудование для перематывания пряжи в бобины. Мотальный карусельный автомат АМ-150К1. Мотальный автомат Аутосук. Техническая характеристика автомата Аутосук.
11. Обучение выполнению нормативов № 7 и 8 5,45 мм автомата Калашникова АК-74 5,45 мм