Эквивалентность состояний конечного автомата

 

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

Состояние S КА M эквивалентно состоянию t КА N тогда и только тогда, когда M, начиная работу из состояния S, будет допускать те же цепочки, что и автомат N, начиная работу из состояния t. Если эти состояния будут начальными, то автоматы M и N эквивалентны S КА M º t КА N. Если эти состояния (S и t) принадлежат одному КА, то этот КА можно упростить, заменив в таблице перехода имена состояний одним и удалив одну из строк.

Рассмотрим эквивалентность, как отношение между двумя состояниями S Q t. Эквивалентность Q рефлексивна, симметрична и транзитивна.

 

Поиск эквивалентных состояний

 

Поиск эквивалентных состояний производится путём разбиения множества состояний КА на подмножества по характеру воздействия входных символов по шагам:

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

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

Для уверенности последний результат нужно ещё раз проверить на воздействие входных символов. После это можно утверждать, что состояния в одном подмножестве эквивалентны.

 

Недостижимые состояния конечного автомата

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

 

Недетерминируемый конечный автомат (НКА)

 

НКА представляет собой обычный КА с той разницей, что значениями его функций переходов являются множества состояний (а не единственные состояния как в КА) и начальное состояние также задаётся как множество.

НКА задаётся:

- Конечным множеством входных символов;

- Конечным множеством состояний;

- Функцией перехода D, которая каждой паре (входной символ, текущее состояние) ставит в соответствие множество новых состояний;

- Подмножеством состояний, выделенных в качестве начального;

- Подмножеством состояний, выделенных в качестве допускающих.

Для распознания множества цепочек всегда легче построить НКА, а затем преобразовать его в КА.

Работу НКА можно интерпретировать двумя способами:

- Для распознания одной и той же цепочки есть множество выборов и если имеется хотя бы одна последовательность, при которой НКА заканчивает работу в допускающем состоянии, то такая цепочка допускается;

- При возникновении альтернативы в переходах НКА, автомат распадается на простые КА, которые работают параллельно и если после поступления символа конца цепочки, хотя бы один из КА находится в допускающем состоянии, то такая цепочка допускается.

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

 

Процедура преобразования НКА в КА

1 Изобразить столбцы для входных символов и записать эти символы;

2 В первой строке записать как множество все начальные состояния;

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

4 В качестве нового состояния, при заполнении следующей строки, использовать множества, которые появились в предыдущей строке;

5 Закончить построение таблицы переходов после того, как будут исчерпаны все варианты множеств, которые появились в таблице;

6 При заполнении столбца с символом конца цепочки, в строке вставить “допустить”, если в множество входит допускающее состояние и “отвергнуть”, если в множестве нет допускающих состояний;

7 Переномеровать состояния и заново заполнить таблицу переходов.