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

В примерах, рассмотренных в предыдущем разделе , мы везде получали детерминированные КА, распознающие соответствующие лексемы, заданные расширенными регулярными выражениями. Работу детерминированного КА легко моделировать программно. Однако для многих реальных лексем соответствующие КА оказываются недетерминированными (НКА), что вызывает затруднение при программной реализации НКА. Выход из этой ситуации подсказывает сама теория автоматов, в которой доказывается, что для НКА М, распознающего язык L=L(M), существует КА распознающий тот же самый язык L=L(M), т.е. L(M)=L( ).

В практическом смысле наиболее важным является сам метод преобразования НКА в КА. Приведём его описание.

Пусть M= (Q ,  , , q₀ , F) . Преобразуем его в

=( , , , , ) следующим образом :

1. =(Q)  это означает , что состояниями автомата являются множества состояний автомата М ;

2. = {q₀};

3. – состоит из всех таких подмножеств s множества Q , что sF ;

4. (S,a)= для всех SQ, где ={P|(q,a) содержит Р для некоторого qS }.

Замечание. Среди состояний могут оказаться недостижимые состояния . Состояние р называется достижимым , если существует такая цепочка w , что (q0, w) *(p , e ). 

Для автомата, заданного графом, это означает, что для достижимого состояния р существует путь, ведущий из q₀ в р, а для недостижимого не существует. Недостижимые состояния можно исключить из множества состояний автомата .

Пример.. Пусть НКА М задана таблицей переходов и множество F={q_f}.

Таблица

Состояние		Вход
	1	2	3
q0	{q0 , q1}	{q0 , q2}	{q0 , q3}
q1	{q1 , qf}	{q1}	{q1}
q2	{q2 }	{q2 , qf }	{q2}
q3	{q3}	{q3}	{q3 , qf}
qf			

1. Построим КА =( , {1 , 2 , 3} , , {q₀} , ) , допускающий язык L(M) . Так как М имеет 5 состояний , то по п.1 должен иметь 32 состояния . Однако не все они достижимы . Мы будем включать в таблицу переходов автомата только достижимые состояния .

2. По п.2 .= {q₀}, обозначим его через А={q₀}= .

3. По п.4 для состояния А={q₀} имеем :

({q₀},1)={q₀ , q₁}= B

({q₀},2)={q₀ , q₂}= C

({q₀},3)={q₀ , q₃}= D

4. Вновь применяем п.4 к полученным состояниям В , С , D и получаем :

({q₀ , q₁ },1)={q₀ , q₁ , q_f }= E

({q₀ , q₁ },2)={q₀ , q₁ , q₂ }= F

({q₀ , q₁ },3)={q₀ , q₁ , q₃ }= G

({q₀ , q₂},1)={q₀ , q₁ , q₂ }=F

({q₀ , q₂},2)={q₀ , q₂ , q_f }=H

({q₀ , q₂},3)={q₀ , q₂ , q₃ }=I

({q₀ , q₃},1)={q₀ , q₁ , q₃ }=G

({q₀ , q₃},2)={q₀ , q₂ , q₃ }=I

({q₀ , q₃},3)={q₀ , q₃ , q_f }=J

Продолжая эту процедуру, получим таблицу переходов автомата (табл. 4.2) .

На основании п.3 можно сделать вывод , что в входят те состояния из которые содержат q_f , поэтому

={E , H , J , K , M , N , P }.

Примерами недостижимых состояний , которые не вошли в , являются состояния : X={q₁ , q₂ } и Y={q₁ , q₂ , q_f } .

Таблица 4.2

Состояния		Вход
	1		2		3
A={q0}	B		C		D
B={q0 , q1}	E		F		G
C={q0 , q2 }	F		H		I
D={q0 , q3 }	G		I		J
E={q0 , q1 , qf }	E		F		G
F={q0 , q1 , q2 }	K		K		L
G={q0 , q1 , q3 }	M		L		M
H={q0 , q2 , qf }	F		H		I
I={q0 , q2 , q3 }	L		N		N
J={q0 , q3 , qf }	G		I		J
K={q0 , q1 , q2 ,qf }	K		K		L
L={q0 , q1 , q2 ,q3 }	P		P		P
M={q0 , q1 , q3 ,qf}	M		L		M
N={q0 , q2 , q3 ,qf }	L		N		N
P={q0 , q1 , q2 ,q3 ,qf }	P		P		P