На главную   ::   Содержание



Теорема о приведении конечного автомата к эквивалентному детерминированному

Определение 1.   Детерминированным конечным автоматом называется пятерка следующего вида: $ A=(Q,\Sigma,M,S,F)$, где $ Q$ -- конечное множество состояний, $ \Sigma$ -- терминальный алфавит, $ M:  Q\times\Sigma\to Q\cup
\{\varnothing\}$ -- функция переходов, $ S\subseteq Q$ -- множество начальных состояний, $ F\subseteq Q$ -- множество финальных состояний.

Замечание 1.   ДКА работает по тактам, за один такт обрабатывая один символ и переходя из состояния в состояние. Есть понятие конфигурации -- это пара: состояние ($ q\in Q$) и цепочка символов ( $ x\in \Sigma^\ast$ -- транзитивное замыкание, т.е. строчка может быть длиной $ 0,1,\dots$ символов). Цепочка допускается ДКА, если он может обработать ее целиком и остановится в финальном состоянии, обозначается это $ (q,x)\vdash^+ (p,\varepsilon)$, $ \varepsilon$ -- пустая цепочка, $ p\in F$.

Определение 2.   Обобщенной функцией переходов для ДКА называется функция $ M': 
Q\times \Sigma^\ast\to Q\cup \{\varnothing\}$, т.е. значение функции -- состояние, в котором будет автомат после обработки некоторой цепочки из некоторого состояния.

Замечание 2.   Теперь легко сказать, когда цепочка допускается ДКА: когда $ M'(q,x)\in F$.

Определение 3.   Языком КА называется множество всех цепочек, допускающихся КА.

Определение 4.   Недетерминированный КА -- это ДКА, для которого $ M:  Q\times \Sigma \to
2^Q$. В этом случае обобщенной функцией переходов называется $ M': 
2^Q\times \Sigma^\ast \to 2^Q$. Цепочка допускается НКА, если $ M'(S,x)\cap F\neq \varnothing$.

Определение 5.   КА с $ \varepsilon$-переходами -- НКА, в котором допускается переход по пустой цепочке, т.е. $ M: 
Q\times(\Sigma\cup\varepsilon)\to 2^Q$.

Замечание 3.   Таким образом, НКА и $ \varepsilon$-КА совершают переходы не между состояниями, а между подмножествами множества состояний $ Q$, т.е. по одному символу автомат переходит сразу в несколько состояний. Но $ \varepsilon$-КА может совершать переход и без получения символа.

Определение 6.   КА называются эквивалентными, если их языки совпадают.

Теорема 1.   По НКА и $ \varepsilon$-КА можно построить эквивалентный ДКА.

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

НКА $ \Rightarrow$ ДКА

Пусть НКА -- $ (Q,\Sigma,M,S,F)$. Тогда ДКА -- $ (2^Q,\Sigma,
M',S,\left\{ p=\{B_1,\dots,B_l\}\in 2^Q: \exists  i  B_i\in F
\right\})$. Это означает, что в качестве состояний ДКА мы рассматриваем все подмножества состояний НКА и переходы совершаем между ними в соответствии с обобщенной функцией перехода НКА. Взяли подмножество и назвали его состоянием. А потом между ними ходим.

$ \varepsilon$-КА $ \Rightarrow$ ДКА

Если между состояниями $ A,B$ существует $ \varepsilon$-переход и из $ B$ нет $ \varepsilon$-дуг, делать следующее: $ A$ -- начальное, то сделать $ B$ начальным. Если $ B$ -- финальное, то сделать $ A$ финальным. Для всех переходов из $ B$ куда либо сделать такие же переходы из $ A$. Для всех переходов откуда-то в $ A$ сделать такие же переходы в $ B$. $ \varepsilon$-дугу удалить.

Если существует цикл из $ \varepsilon$-дуг, соединяющий $ A$ и $ B$, то все состояния цикла объединяются в новое состояние, все $ \varepsilon$-дуги удаляются и для всех состояний цикла входящие и выходящие дуги копируются в это новое состояние.

Поскольку $ \varepsilon$-переходов конечное число, мы когда-нибудь закончим приведение к ДКА. $ \blacksquare$


На главную   ::   Содержание