Недетерминированные конечные автоматы

Регулярные выражения и конечные автоматы

Алгоритм распознавания на основе диаграммы состояний

Автоматные грамматики и диаграмма состояний

Рассмотрим грамматику G(Z), которая содержит правила:

Z: = U0|V1; U: = Z1|1; V: = Z0|0.

Изобразим графически процесс построения сентенциальных форм. Назовём это диаграммой состояния, где каждый нетерминал есть некоторое состояние. Существует также начальный символ S – начальное состояние, SÏNUå.. Каждому правилу вида Q:=T, где TÎVT, QÎVN поставим в соответствие дугу, исходящую из начального символа и направленную в состояние, помеченное Q, а каждому правилу вида Q: = RT, где TÎVT, Q,RÎVN поставим в соответствие дугу, исходящую из вершины R и направленную в вершину, помеченную Q. Будем использовать диаграмму состояний для распознавания цепочки.

Диаграмма состояний:

S

Z

V

U

Ошибка

Пусть имеем цепочку x, содержащую n терминальных символов. Первым текущим состоянием считать начальное состояние S.

1. Начать с самого левого терминала цепочки и повторять шаг 2, пока не будет достигнут правый её конец.

2. Сканировать следующую литеру цепочки x. Продвинуться по дуге, помеченной этим терминалом, переходя к следующему текущему состоянию. Если на каком-то шаге такой дуги не оказывается, то цепочка x не является предложением языка, генерированного рассматриваемой грамматикой. Если конец цепочки достигнут, она является предложением тогда и только тогда, когда последнее текущее состояние есть Z(начальный символ).

Разберём цепочку

0 1 1 0 0 1

^V _Z

^V _Z

Цепочка является предложением языка сгенерированного данной грамматикой.

Если взять цепочку 11 1111, сразу будет ошибка.

Все символы в языках программирования попадают в один из следующих классов:

1) идентификаторы;

2) служебные слова;

3) целые числа;

4) операторы;

5) разделители;

6) комментарии.

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

ДКА={ Q, S, δ, S, Z }

ДКА – детерминированный конечный автомат;

Q – множество состояний (алфавит нетерминальных символов);

S - множество входных символов (алфавит терминальных символов);

δ – функция отображения (Q×S Q);

S – начальное состояние;

Z– конечное состояние.

Будем говорить, что ДКА допускает цепочку t, если δ (St)=P, где РÎZ.

Можно переписать правила из примера следующим образом:

δ (U0)=Z, δ (V1)=Z, δ (Z1)=U, δ (S1)=U, δ (Z0)=V, δ (S0)=V.

ДКА с состояниями S_i и входной литерой t_j можно представить матрицей B=||b_ij||, элемент которой b_ij=k, где k – номер состояния, и существуют функции отображения δ (S_i, t_j)=S_k.

Положение осложняется, если грамматика G содержит правила вида:V: = UT; W: = UT, то есть одинаковые правые части. В диаграмме состояний есть 2 дуги, помеченные символом Т, исходящих из U. Отображение δ становится неоднозначным, и поэтому автомат становится недетерминированным.

Пример:

S

Z

U

V

Q

НКА { Q, S, δ, S, Z }, δ(RT) = { W_i }, где W_i Î Q.

Напишем правила через функцию отображения:

δ(S0)=V,Q; δ(S1)=U,Q; δ(Q0)=V,Q; δ(Q1)=U,Q;

δ(U1)=Z; δ(V0)=Z; δ(Z1)=Z; δ(Z0)=Z.

Предположим, у нас есть цепочка 01001. Рассмотрим ее разбор по шагам:

Шаг	Текущее состояние	Остаток входной цепочки	Возможные состояния	Выбранное состояние
	S		V,Q	Q
	Q		U,Q	Q
	Q		V,Q	V
	V		Z	Z
	Z		Z	Z

Для любой регулярной грамматики G можно построить диаграмму состояний, а следовательно, НКА. При работе НКА возникает неоднозначность при выборе следующего состояния, если существуют несколько дуг с одинаковой пометкой. Поэтому, прежде чем прийти к выводу о том, что строка не может быть принята НКА, необходимо перепробовать всевозможные последовательности переходов. Следовательно, читать входную цепочку необходимо не один раз, а Õ(n_i), где n-число возможных переходов на j шаге.

Пусть мы имеем НКА {Q, S, δ, S, Z}. Нужно построить ДКА{Q’ S, δ’, S’, Z’}.

W

0 0

S

Z

1 0 0

1

N

1 0