Конечный автомат может содержать лишние состояния двух типов: недостижимые и эквивалентные состояния.
ОпределениеДва различных состояния и в конечном автомате называются 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 – Граф исходного конечного автомата М
Последовательность устранения недостижимых состояний КА имеет вид:
Q0 = {A};
Q1 = {A, B, C};
Q2 = {A, B, C, D, E};
Q3 = {A, B, C, D, E}; т.к. Q2 = Q3, то 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 |
|
Рисунок 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 Взаимосвязь способов определения грамматик
Регулярные грамматики, регулярные выражения и конечные автомата – три основных способы определения регулярных языков, между которыми существует полное соответствие. Разработаны алгоритмы преобразования одной формы определения в другую. При работе с языками программирования наибольший практический интерес представляют преобразования регулярной грамматики в конечный автомат. Рассмотрим его.