Конечные распознаватели. Основные понятия

Определить принадлежность заданной (входной) цепочки заданному регулярному языку можно с помощью конечного распознавателя. Конечный распознаватель – это конечный автомат Рабина-Скотта, который определяется пятёркой: A=<S, X, s₀, , F>, где

S – конечное непустое множество состояний;

X – конечное непустое множество входных символов;

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

: SXS – функция переходов, которая паре (состояние, входной символ) ставит в соответствие новое состояние (состояние перехода);

FS – множество допускающих состояний.

Конечный распознаватель можно представить как устройство с одним входом, которое в момент времени t может находиться в некотором состоя-нии s_tS, а на вход поступает символ x_tX из входной цепочки. Будем говорить, что распознаватель в момент времени t находится в состоянии s_t и обрабатывает символ x_t. В соответствии с функцией переходов распознаватель перейдёт в новое состояние s_t+1=( s_t, x_t), s_t+1S и в следующий момент времени t+1 будет находиться в состоянии s_t+1 и обрабатывать следующий символ x_t+1 входной цепочки. В начальный момент времени t=0 распознаватель находится в начальном состоянии s₀ и обрабатывает первый символ входной цепочки. На каждом шаге распознаватель обрабатывает новый (следующий за предыдущим) символ цепочки. Если после обработки последнего символа входной цепочки распознаватель окажется в допускаю-щем состоянии s_kF, то входная цепочка принадлежит языку (цепочка допускается распознавателем), иначе – не принадлежит языку (цепочка отвергается распознавателем). Другими словами, конечный распознаватель допускает входную цепочку, если она переводит его из начального состояния в одно из допускающих (позволяет “связать” начальное состояние с одним из допускающих). Множество (возможно, бесконечное) всех цепочек, допускаемых конечным распознавателем А, образует язык L(A), допускаемый распознавателем A.

Конечный распознаватель можно задать таблицей, строки которой соответствуют входным символам, а столбцы – состояниям. Первый столбец соответствует начальному состоянию, а столбцы, соответствующие допускающим состояниям будем отмечать символом “1”. Если распознаватель из состояния s_j при обработке символа x_i переходит в состояние s_k, то в клетке таблице на пересечении строки x_i и столбца s_j записывается состояние s_k.

Пример.

					1
	s0	s1	s2	s3	s4
ц	s2	s2	s2	s4	s4
.	s3	s3	s4
+	s1
-	s1

Этой таблицей представлен конечный распознаватель, имеющий шесть состояний S={s0, s1, s2, s3, s4, Error} и четыре входных символа X={ц, ., +, -} . Состоянию Error не соответствует столбец таблицы. Это особое состояние ошибки, из которого невозможен переход в какое либо состояние, отличное от него, а, следовательно, из него недостижимо допускающее состояние. Если в процессе обработки входной цепочки распознаватель переходит в состояние ошибки, то цепочка отвергается независимо от необработанной её части. Переходам в состояние ошибки соответствуют пустые клетки. Допускающее состояние одно F={s4} , обозначено символом “1” в верхней строке.

Конечный распознаватель можно задать ориентированным графом. Вершинам графа соответствуют состояния, а дугам – переходы. В вершинах записываются состояния, а на дугах – входые символы. Если распознаватель из состояния s_j при обработке символа x_i переходит в состояние s_k, то из вершины s_j проводится дуга, отмеченная символом s_i, в вершину s_k. Вершина, соответствующая состоянию ошибки, и дуги, ведущие в состояние ошибки, в графе не изображаются (подразумеваются). Начальное состояние отмечается стрелочкой, а допускающие состояния выделяются жирной линией.

Пример.

Граф распознавателя, представленного выше таблицей.

ц

ц

ц . ц

+

- .

ц

.

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

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

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

Конечный недетерминированный распознаватель определяется пятёркой: A=<S, X, S₀, , F>, где

S – конечное непустое множество состояний;

X – конечное непустое множество входных символов;

S₀ S – множество начальных состояний;

: SX2^S, где 2^S обозначает булеан S, т.е. множество всех подмножеств множества S – функция переходов, которая паре (состояние, входной символ) ставит в соответствие подмножество состояний;

FS – множество допускающих состояний.

Недетерминированный распознаватель, также как и детерминированный, можно задать таблицей или графом. В клетках таблицы недетерминированного распознавателя записываются множества состояний переходов, а столбцы, соответствующие начальным состояниям, отмечаются символом “”. В графе недетерминированного распознавателя из одной вершины могут выходить различные дуги, отмеченные одним и тем же входным символом.

Пример.

Таблица недетерминированного распознавателя.

						1
	s0	s1	s2	s3	s4	s5
ц	s1,s3	s1,s3			s5	s5
.	s4		s4	s5
+	s1,s2
-	s1,s2

Пример.

Граф недетерминированного распознавателя.

. . ц

+,-

ц

ц,+,-

ц

ц ц .

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

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

Очевидно, что детерминированные конечные распознаватели являются подклассом недетерминированных конечных распознавателей.

Недетерминированный распознаватель, который может перейти на некотором шаге из состояния в состояние без обработки символа входной цепочки, называется недетерминированным конечным распознавателем с -переходами.

Конечный недетерминированный распознаватель с -переходами определяется пятёркой: A=<S, X, S₀, , F>, где

S – конечное непустое множество состояний;

X – конечное непустое множество входных символов;

S₀ S – множество начальных состояний;

: S{X}2^S, где 2^S обозначает булеан S, т.е. множество всех подмножеств множества S – функция переходов, которая паре (состояние, входной символ) или паре (состояние, ) ставит в соответствие подмножество состояний;

FS – множество допускающих состояний.

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

Пример.

Таблица недетерминированного распознавателя с -переходами.

							1
	s0	s1	s2	s3	s4	s5	s6
ц		s1,s3			s5	s5
.			s4	s5
+	s1,s2
-	s1,s2
	s1,s2					s6

Пример.

Граф недетерминированного распознавателя с -переходами.

ц

ц

+,-, . ц



+,-, ц

.

Недетерминированные конечные распознаватели являются подклассом недетерминированных конечных распознавателей с -переходами.

Два конечных распознавателя (детерминированных, недетерминированных с -переходами или без них) называются эквивалентными, если равны допускаемые ими языки. Процедуру получения недетерминированного конечного распознавателя без -переходов, эквивалентного заданному недетерминированному конечному распознавателю с -переходами назовём устранением -переходов. Процедуру получения детерминированного конечного распознавателя, эквивалентного заданному недетерминированному конечному распознавателю назовём преобразованием недетерминированного конечного распознавателя в детерминированный.