Детерминизация конечных автоматов

Для того, чтобы построить соответствующее таким грамматикам автоматы, можно рассматривать переходы FавтоматаQV_T в множество подмножествQ( т.е. вP(Q)). При этом

P(Q)=2^Q.

Будем называть недетерминированным конечным автоматом Sпятерку объектовS = <Q,V_T,q₀,F,K>, где интерпретацияQ,V_T,q₀,Kтакая же, как и раньше, аF – отображениеQV_Tв P(Q).

Определение цепочек, допускаемых автоматом, остается прежним, но если в детерминированном автомате последовательность конфигураций однозначно определялась заданием входной цепочки, так как из каждой конфигурации автомат мог перейти не более чем в одну конфигурацию, то в недетерминированном случае это не так. Поэтому при интерпретации определения "цепочка Xдопущена" как (q₀,x)├(q, )&qK необходимо при анализе цепочки, моделируя работу автомата, перебрать варианты выполнения тактов, чтобы найти тот (или те), которые приводят в заключительную ситуацию. В силу тех же соображений (тождественность движений по графу и при порождении цепочки, и при ее допускании) можем утверждать, что для любой грамматики G может быть построен конечный автоматA(в общем случае недетерминированный), такой, чтоL(G)=L(A) .Соответствия между параметрами грамматики и автомата остаются те же.

Возникает естественный вопрос о соотношении класса языков, допускаемых детерминированными и недетерминированными автоматами. Ясно, что для любого детерминированного автомата Aсуществует недетерминированныйA'допускающий тот же самый язык (достаточно в качествеA' взятьА). Но верно ли обратное? Ответ на этот вопрос дает следующая теорема.

Теорема 1.Если L=L(A)для некоторого недетерминированного автоматаA, то найдется конечный автомат A' такой, что L(A')=L(A).

Доказательство:

Пусть дан недетерминированный конечный автомат А = <Q,V_T,q₀,F,K>. Построим соответствующий детерминированный автоматА’= <Q’,V_T,q₀’,F’,K’>

Q’ = P(Q) . При этом множество состояний будем обозначать как .

q₀’=[q₀].

K’ = {/K }

F’(, a)=

Несложно доказать методом математической индукции, что для любого I

([q₀],XY) ├ⁱ_A’(B,Y)B={p/ (q₀,XY) ├ⁱ_A(p,Y)}

X=i.

Значит, для любой цепочки Х

([q₀],X) ├ⁱ_A’(B,)B={p/ (q₀,X) ├ⁱ_A(p,)}

Поэтому, в случае BK’, т.е. если Х – цепочка, допускаемая детерминированным автоматом, то в исходном недетерминированном автомате существует путь из начального в конечное состояние при чтении этой цепочки, и, следовательно,L(A)=L(A’).

Т.о., сопоставляя доказанные утверждения, получаем:

Класс А-языков и класс языков, распознаваемых конечными автоматами, совпадает.

Так, например, для автомата, представленного на рис. 5, соответствующий детерминированный автомат представлен на рис. 6.

Рис.6

Здесь F(S,a)= [S,A] = A’

F([S,A], a) = [S,A]

F([S,A],b) = [A, K] = K’

F([A,K],b)= [A, K] = K’

Для автомата на рис. 7а детерминированный автомат представлен на рис.7b.

Рис.7

Алгоритм построения детерминированного автомата по недетерминированному:

Строим начальное состояние q₀’= [q₀], помечаем его как начальное.

Для каждого состояния, построенного на предыдущем шаге, строим

F(q_i’,a) для всехaV_T. Если для какого-нибудь из построенных состояний функция перехода ещё не построена, возвращаемся к шагу 2.

Помечаем как конечные все состояния q_i’=/ K.

Конечность процесса обеспечивается конечностью множества P(Q).