Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7

Вид материала

Конспект

Содержание 6.3. Детерминизация недетерминированных автоматов A, то найдется конечный автомат A'

Подобный материал:

• Учебное пособие тверь 2008 удк 519. 876 (075. 8 + 338 (075. 8) Ббк 3817я731-1 + 450., 2962.9kb.
• Тексты лекций Москва 2008 удк 339. 9(075. 8) Ббк 65. 5я73-2, 1528.45kb.
• Программно-технический комплекс Учебное пособие Новочеркасск юргту (нпи) 2010. Удк, 3911.73kb.
• Удк 152. 27 (075. 8) + 157 (075. 8) + 152. 3 (075, 60.12kb.
• Краткий конспект лекций Кемерово 2002 удк: 744 (075), 1231.26kb.
• Методические указания по курсу Новосибирск 2004 ббк ю 937. 4 Удк 152. 26 (075), 802.63kb.
• Москва 2011 ббк 63. 3 (2)я 7 к 90 удк 947 (075) История России, 110.08kb.
• Курс лекций Гродно 2005 удк 631. 1 (075., 1193.16kb.
• Удк 070(075. 8) Ббк 76. 01я73, 5789.66kb.
• Удк 339. 9(470)(075. 8) Ббк, 7329.81kb.

6.3. Детерминизация недетерминированных автоматов

Будем называть недетерминированным конечным автоматом S пятерку объектов S = _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' взять А). Но верно ли обратное? Ответ на этот вопрос дает следующая теорема.

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

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

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

1. Q’ = P(Q) . При этом множество состояний будем обозначать как .
   
2. q₀’=[q₀].
   
3. K’ = { / K }.
   
4. F’( , a)= .
   

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

([q₀],xy) ├ⁱ_A’(B, y)  B={p/ (q₀, xy) ├ⁱ_A(p,y)} при x=i.

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

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

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

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

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

Так, например, для автомата, представленного на рис. 2, соответствующий детерминированный автомат, порождающий L(G₉), представлен на рис. 4.



Рис.4


Для этого автомата F(S,a)= [S,A] = A’,

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

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

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

Для автомата на рис. 5,а детерминированный автомат представлен на рис.5,б.

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

1. Строим начальное состояние q₀’= [q₀], помечаем его как начальное.
   
2. Для каждого состояния q_i’, построенного на предыдущем шаге, строим F(q_i’, a) для всех aV_T. Если для какого-нибудь из построенных состояний функция перехода ещё не построена, возвращаемся к шагу 2.
   
3. Помечаем как конечные все состояния q_i’= / K  .
   

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




Рис.5