Конечные автоматы: преобразователи и распознаватели

Пример 4.4. Рассмотрим язык L, состоящий из всех слов в алфавите $$\Sigma =\{ a, b\}$$, которые начинаются на aa и содержат нечетное число символов b.

Для выделения слов, начинающихся на aa, создадим начальное состояние q0, которое первый символ a будет переводить в состояние q1, а второй символ a будет переводить q1 в состояние q2. Ясно, что все слова, которые начинаются на ab, ba, bb, сами не входят в язык L и все их продолжения также ошибочны. Заведем для них "ошибочное" состояние q!. Остальные слова естественно разбиваются на два класса: те, в которых четное число символов b, и те, в которых число таких символов нечетно (они и принадлежат L ).

Так как после получения aa число b четно, то для представления слов первого класса будем использовать состояние q2, а для представления слов второго - создадим состояние q3, которое и будет заключительным. В результате получаем автомат, диаграмма которого представлена на рис. 4.2. (Мы отмечаем на рисунках диаграмм начальное состояние стрелкой $$\to,$$ а заключительные состояния - двумя окружностями).

Проверим работу этого автомата, например, на входном слове w=aaababa. При его чтении порождается следующая последовательность конфигураций:

Заключительное состояние этого вычисления q2 не является заключительным. Следовательно, $$w \notin L_{A}$$. Если же мы рассмотрим в качестве входа слово w1= w b= aaababab, то, продолжив на один шаг приведенное выше вычисление, получим, что $$(q_0, w_1) \vdash_A^* (q_3, \varepsilon)$$. Следовательно, $$w_{1} \in L_{A}$$.

Мы проверили, что на двух входах автомат A работает верно. Как установить, что он построен корректно, т.е. верно работает на всех входных словах и распознает L? Типичная схема доказательства правильности конечного автомата такова:

Применим эту схему к доказательству правильности, построенного выше автомата A. Языки, связанные с состояниями этого автомата, фактически, уже были определены при его построении. Уточним их:

Правильность определения языков L(q0), L(q1) и L(q!) следует непосредственно из определения A. Самое короткое слово, переводящее q0 в q2 - aa, и оно принадлежит L(q2). Аналогично, самое короткое слово, переводящее q0 в q3 - aab, и оно принадлежит L(q3). Предположим теперь, что для каждого слова w длины <= n выполнено условие (*):

w переводит начальное состояние q0 в $$q_{i} (i=2,3) \Leftrightarrow w \in L(q_{i})$$.

Покажем, что оно будет выполнено и для всех слов длины n +1.

Пусть |w|=n+1. Тогда $$w = w' \alpha$$, где $$\alpha \in \{ a, b \}$$. Так как |w'|=n, то для w' выполнено условие (*). Поэтому, если w' переводит q0 в q2, то это слово начинается с aa и содержит четное число b. При $$\alpha =a$$ слово w переводит q0 в q2 и также начинается с aa и содержит четное число b, а при $$\alpha = b$$ слово w переводит q0 в q3, начинается с aa и содержит нечетное число b, т.е. принадлежит L.

Аналогично, если w' переводит q0 в q3, то это слово начинается с aa и содержит нечетное число b. При $$\alpha =a$$ слово w также переводит q0 в q3 и также начинается с aa и содержит нечетное число b, а при $$\alpha = b$$ w переводит q0 в q2, оно начинается с aa и содержит четное число b. Обратно, если $$\alpha =a$$, то слово w переводит q0 в $$q_{i} (i=2,3) \Leftrightarrow$$ w' переводит q0 в qi\ (i=2,3) и условие (*) выполнено, так как четность числа букв b в w и в w' одинакова. Если же $$\alpha = b$$, то из определения автомата A следует, что слово w переводит q0 в $$q_{2} \Leftrightarrow$$ w' переводит q0 в q3 и w переводит q0 в $$q_{3} \Leftrightarrow$$ w' переводит q0 в q2. Так как четность числа букв b в w и в w' разная, то и в этом случае условие (*) выполнено. Для завершения доказательства осталось заметить, что единственным заключительным состоянием автомата A является q3 и поэтому LA = L(q3) = L.

Произведение автоматов

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

Пусть $$M_{1} = <\Sigma , Q_{1}, q_{0}^{1}, F_{1}, \Phi _{1}>$$ и $$M_{2} = <\Sigma , Q_{2}, q_{0}^{2}, F_{2}, \Phi _{2}>$$ - два конечных автомата с общим входным алфавитом $$\Sigma,$$ распознающих языки L1 и L2, соответственно. Определим по ним автомат M= $$<\Sigma , Q, q_{0}, F, \Phi >$$, называемый произведением M1 и M2 (M= M1 x M2), следующим образом. $$Q= Q_{1} x Q_{2} =\{ (q, p) | q \in Q_{1}, p \in Q_{2}\}$$, т.е. состояния нового автомата - это пары, первый элемент которых - состояние первого автомата, а второй - состояние второго автомата. Для каждой такой пары (q,p) и входного символа $$a \in \Sigma$$ определим функцию переходов: $$\Phi ((q,p), a) = (\Phi _{1}(q,a), \Phi _{2}(p,a))$$. Начальным состоянием M является пара q0= (q01, q02), состоящая из начальных состояний автоматов-множителей. Что касается множества заключительных состояний, то оно определяется в зависимости от операции над языками L1 и L2, которую должен реализовать M.

Теорема 4.1.

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

Лемма 4.2. Для любых двух состояний (q,p) и (q', p') автомата M и любого входного слова w слово w переводит (q,p) в (q', p') в автомате M тогда и только тогда, когда оно переводит q в q' в автомате M1 и p в p' в автомате M2.

Лемма устанавливается индукцией по длине слова w.

Следствие4.1.1. Класс конечно автоматных языков замкнут относительно теоретико множественных операций объединения, пересечения и разности.

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

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

Определение 4.8. Недетерминированный конечный автомат (НКА) - распознаватель - это система вида

включающая следующие компоненты:

Для $$a \in \Sigma$$ значение $$\Phi (q, a)$$ - это множество состояний в каждое из которых может перейти автомат из состояния q, когда получает на вход символ a. $$\Phi (q, \varepsilon )$$ - это множество состояний в каждое из которых может перейти автомат из состояния q без чтения символа на входе.

Как и для детерминированных автоматов, функцию переходов можно представить с помощью набора команд-программы: для каждой пары $$q \in Q$$ и $$a \in \Sigma$$ и каждого состояния $$q' \in \Phi (q, a)$$ в программу помещается команда q a -> q', и для каждого состояния $$q' \in \Phi (q, \varepsilon )$$ в программу помещается команда q -> q'. Отличие от детерминированного случая состоит в том, что для одной пары $$q \in Q$$ и $$a \in \Sigma$$ в программе может быть несколько команд вида q a -> q' или не быть ни одной такой команды. Кроме того, могут появиться $$\varepsilon$$ -команды (пустые переходы) вида q -> q', означающие возможность непосредственного перехода из q в q' без чтения символа на входе.

При табличном задании функции $$\Phi$$ в таблице появляется (m+1) -ый столбец, соответствующий пустому символу $$\varepsilon$$ и на пересечении строки q и столбца $$a \in (\Sigma \cup \{ \varepsilon \} )$$ стоит множество состояний $$\Phi (q,a)$$.

Для недетерминированного автомата $$M = <\Sigma , Q, q_{0}, \Phi >$$ в диаграмме DM=(Q, E) с выделенной начальной вершиной q0 и множеством заключительных вершин F ребра взаимно-однозначно соответствуют командам: команде вида q a -> q' $$(a \in \Sigma )$$ соответствует ребро (q,q' ), с меткой a , а команде вида q -> q' соответствует ребро (q,q' ), с меткой $$\varepsilon$$ .

Скажем, что заданный последовательностью ребер путь p=e1e2 ... eT в диаграмме DM несет слово w=w1w2 ... wt (t <= T), если после удаления из него "пустых" ребер (т.е. ребер с метками $$\varepsilon$$ ) остается последовательность из t ребер $$p'=e_{j_1}e_{j_2} \ldots e_{j_t}$$, метки которых образуют слово w , т.е. wi - это метка ребра $$e_{j_i}\ (1 \leq i \leq t)$$. Очевидно, это эквивалентно тому, что последовательность меток на ребрах пути p имеет вид $$\varepsilon^{k_1}w_1\varepsilon^{k_2}w_2 \ldots \varepsilon^{k_t}w_t \varepsilon^{k_{t+1}}$$, где kj >= 0 (j=1,2, ... , t+1) и $$\ t + \sum_{j=1}^{t+1} k_j = T$$.

Слово w переводит q в q' в диаграмме DM, если в ней имеется путь из q в q' который несет w .

На недетерминированные автоматы естественным образом переносится определение конфигураций и отношения перехода между ними.

Определение 4.9. Назовем конфигурацией НКА $$M = <\Sigma , Q, q_{0}, F, \Phi , >$$ произвольную пару вида (q, w), в которой $$q \in Q$$ и $$w \in \Sigma ^{*}$$. Определим отношение $$\vdash_M$$ перехода из одной конфигурации в другую за один шаг:

или

Как и для ДКА, через $$\vdash_M^*$$ обозначим рефлексивное и транзитивное замыкание отношения $$\vdash_M$$.

Внешне определение распознавания слов НКА совпадает с определением для ДКА.

Определение 4.10. НКА M распознает (допускает, принимает) слово w, если для некоторого $$q \in F$$ \ $$(q_0, w) \vdash_M^* (q, \varepsilon).$$

Язык LM, распознаваемый НКА M, состоит из всех слов, распознаваемых автоматом:

Отличие состоит в том, что у НКА может быть несколько различных способов работы (путей вычисления) на одном и том же входном слове w. Считаем, что НКА распознает (допускает, принимает) это слово, если хотя бы один из этих способов приводит в заключительное состояние из F.

Из определения диаграммы DM непосредственно следует, что НКА M распознает слово w, тогда и только тогда, когда существует такое заключительное состояние $$q \in F$$, что в диаграмме DM слово w переводит q0 в q. Иными словами, в DM имеется путь из q0 в q, на ребрах которого написано слово w (с точностью до меток $$\varepsilon$$ ).

Пример 4.1. Рассмотрим НКА $$N_{1} = < \{ a, b\} , \{ 0,1,2,3, 4\} , 0, \{ 3\} , \Phi >$$, где

Его диаграмма $$D_{N_1}$$ представлена ниже на рис. 4.3.

Рассмотрим работу этого автомата на слове ababa:

Так как 3 - заключительное состояние, то $$ababa \in L_{N1}$$. Заметим, что у автомата N1 имеются и другие способы работы на этом слове, не ведущие к заключительному состоянию. Например, он может после чтения каждого символа оставаться в состоянии 0. Но чтобы слово допускалось, достаточно существовать хотя бы одному "хорошему" способу.

Очевидно, что детерминированные конечные автоматы являются частными случаями недетерминированных. Естественно спросить, распознают ли недетерминированные конечные автоматы больший класс языков чем детерминированные? Следующая теорема показывает, что классы языков, распознаваемых НКА и ДКА совпадают.

Теорема 4.2. (Детерминизация НКА)

Для каждого НКА M можно эффективно построить такой ДКА A, что LA = LM.

Доказательство Пусть $$M= <\Sigma , Q, q_{0}, F, \Phi >$$ - НКА. Процедура построения по нему эквивалентного ДКА состоит из двух этапов: на первом по M строится эквивалентный ему НКА M1, в программе которого отсутствуют переходы по $$\varepsilon,$$ а на втором этапе по M1 строится эквивалентный ДКА A.

Этап 1. Устранение пустых переходов.

Рассмотрим поддиаграму автомата M, в которой оставлены лишь ребра, помеченные $$\varepsilon:$$ $$D_{\varepsilon } =(Q, E_{\varepsilon })$$, где $$E_{\varepsilon } =\{ (q, q') | q' \in \Phi (q,\varepsilon )\}$$.

Пусть $$D_{\varepsilon *} =(Q, E_{\varepsilon }^{*})$$ - это граф достижимости (транзитивного замыкания) для $$D_{\varepsilon }$$. Тогда $$E_{\varepsilon }^{*} =\{ (q, q') | q=q'$$ или в $$D_{\varepsilon }$$ имеется путь из q в q'}.

Определим НКА $$M_{1}= <\Sigma , Q_{1}, q_{0}, F_{1}, \Phi _{1} >$$ следующим образом: $$Q_{1} = \{ q_{0}\} \cup \{ q | \ существуют \ такие \ q' \in Q и a \in \Sigma , что \ q \in \Phi (q', a) \}$$, т.е. кроме начального остаются лишь те состояния, в которые входят "непустые" ребра. $$F_{1} =\{ q | \ существует \ такое \ q' \in F, что \ (q,q') \in E_{\varepsilon }^{*} \}$$, т.е. к заключительным состояниям M добавляются состояния, из которых можно было попасть в заключительные по путям из $$\varepsilon$$ -ребер.

Для каждой пары $$q' \in Q, a \in \Sigma$$ полагаем $$\Phi _{1}(q,a) =\{ r |\ существует \ такое \ q' \in F , \ что \ (q,q') \in E_{\varepsilon }^{*} и \ r \in \Phi (q',a) \}$$, т.е. в DM1} имеется a -ребро из q в r, если в DM был (возможно пустой) путь из $$\varepsilon$$ -ребер в некоторое состояние q', из которого a -ребро шло в r.

Из этого определения непосредственно следует, что в НКА M1 нет пустых переходов по $$\varepsilon.$$ Установим эквивалентность M и M1.

Лемма 4.1. $$L_{M_1} = L_M$$.

Доказательство. Пусть w=w1w2... wt - произвольное входное слово. Предположим, что $$w \in L_{M_1}$$. Это означает, что в диаграмме $$D_{M_1}$$ имеется путь p=e1e2 ... et (e1= (q0=r0,r1), ei=(ri-1,ri), i=2,..., t) из q0 в некоторое состояние $$r_{t} \in F_{1}$$, который несет слово w, т.е. ребро ei помечено символом wi. Из определения функции $$\Phi _{1}$$ непосредственно следует, что для любого ребра ei(ri-1, ri) этого пути в диаграмме DM имеется путь из ri-1 в ri, начало (возможно пустое) которого состоит из $$\varepsilon$$ -ребер, а последнее ребро помечено символом wi. Объединив эти пути, получим в диаграмме DM путь из q0 в rt , который несет слово w. Так как $$r_{t} \in F_{1}$$, то либо $$r_{t} \in F$$, либо в DM имеется путь по $$\varepsilon$$ -ребрам из rt в некоторое состояние $$r' \in F$$. В обоих случаях в DM имеется путь из q0 в заключительное состояние, который несет слово w, и следовательно, $$w \in L_{M}$$.

Обратно, пусть $$w \in L_{M}$$. Тогда в DM имеется путь из q0 в некоторое заключительное состояние r, который несет слово w. Пусть r0=q0, а ri - это состояние этого пути, в которое приводит ребро с меткой wi (i= 1,... , t). Рассмотрим отрезок этого пути между вершинами r_{i-1} и ri. Последнее ребро этого отрезка имеет метку wi, а все предыдущие (если они имеются) помечены $$\varepsilon.$$ Тогда по определению $$\Phi _{1}$$ в диаграмме $$D_{M_1}$$ между r_{i-1} и ri имеется ребро с меткой wi. Объединив эти ребра, получим в $$D_{M_1}$$ путь из q0 в rt. Так как либо $$r_{t}=r \in F$$, либо в DM из rt имеется путь из $$\varepsilon$$ -ребер в $$r \in F$$, то из определения F1 следует, что $$r_{t} \in F_{1}$$. Таким образом, $$w \in L_{M_1}$$.

Этап 2. Детерминизация.

Идея детерминизации состоит в том, что состояниями ДКА объявляются подмножества состояний НКА. Тогда для каждого такого подмножества T и входного символа a однозначно определено множество состояний T', в которые НКА может попасть из состояний T при чтении a.

Определим по НКА $$M_{1}= <\Sigma , Q_{1}, q_{0}, F_{1}, \Phi _{1} >$$ ДКА $$A = <\Sigma , Q^{A}, q_{0}^{A}, F^{A}, \Phi ^{A}>$$ следующим образом.

Ясно, что A - детерминированный конечный автомат. Следующая лемма устанавливает связь между его вычислениями и вычислениями исходного НКА.

Лемма 4.4. Для любой пары состояний Q', Q'' из QA и любого слова $$w \in \Sigma ^{*}$$ имеем

Доказательство. Применим индукцию по длине слова w.

Базис. Пусть |w|=0, тогда $$w=\varepsilon$$, Q' = Q'' и утверждение выполнено. Пусть теперь |w|=1 и $$w= a \in \Sigma$$. Тогда утверждение леммы следует непосредственно из определения $$\Phi ^{A(Q', a)}$$.

Шаг индукции. Предположим, что лемма справедлива для всех слов длины <= k, и пусть |w| = k+1. Выделим в w первый символ: w=aw'. Пусть $$\tilde{Q}$$ - это такое состояние, что $$(Q', a) \vdash_A \tilde{Q}, \varepsilon)$$. Тогда $$(\tilde{Q}, w^\prime) \vdash_A^* (Q^{\prime\prime},\varepsilon)$$. Так как |w'|=k, то по индукционному предположению это эквивалентно следующему: $$Q^{\prime\prime}= \{ r\ |\ \text{ существует такое } q^\prime \in \tilde{Q}, \text{ что }\ (q,w^\prime) \vdash_{M_1}^* (r, \varepsilon)\}$$. Но из определения $$\Phi ^{A}$$ следует, что $$\tilde{Q}$$ $$=\{ q | \ существует \ такое \ q' \in Q', \ что \ q \in \Phi _{1}(q', a) \}$$. Объединив, эти два равенства, получаем: $$Q^{\prime\prime}= \{ r\ |\ \text{ существует такое } q^\prime \in Q^\prime, \text{ что }\ (q,w) \vdash_{M_1}^* (r, \varepsilon)\}$$.

Для завершения доказательства теоремы покажем с помощью леммы 4.4, что $$L_A = L_{M_1}$$.

Действительно, если слово w переводит состояние q0 в некоторое $$q \in F_{1}$$ в автомате M1, то, положив в лемме Q' ={ q0}, получим, что $$q \in Q''$$ для состояния Q'', такого, что $$(Q', w) \ vdash_{A}^{*} (Q'',\varepsilon )$$. Но тогда $$Q'' \in F^{A}$$ и $$w \in L_{A}$$.

Обратно, если $$w \in L_{A}$$, то для некоторого $$Q'' \in F^{A}$$ имеем $$(\{q_0\}, w) \vdash_A^* (Q^{\prime\prime},\varepsilon)$$. Тогда в Q'' имеется некоторое состояние $$q \in F_{1}$$ и по лемме 4.4 в автомате $$M_1 \ (q_0,w) \vdash_{M_1}^* (q, \varepsilon)\}$$, т.е. $$w \in L_{M1}$$.

Пример 4.2. Применим процедуру из теоремы о детерминизации к НКА N1 из примера 4.3.

На первом этапе получаем $$E_{\varepsilon }^{*} =\{ (2,0), (1, 4), (3, 1), (4, 1)\}$$ и НКА M1 без пустых переходов, представленный на следующей диаграмме.

Заметим, что состояние 4 исчезло, так как в автомате N1 в него можно было попасть только по $$\varepsilon$$ -переходу.

На втором этапе детерминизируем M1. ДКА A будет иметь 16 состояний: $$Q^{A}=\{ \varnothing , \{ 0\} , \{ 1\} , \{ 2\} , \{ 3\} ,\{ 0,1\} , \{ 0,2\} , \{ 0,3\} , \{ 1,2\} , \{ 1,3\} , \{ 2,3\} , \{ 0,1,2\} ,\{ 0,1,3\} ,\{ 0,2,3\} ,\{ 1,2,3\} ,\{ 0,1,2, 3\} \}$$.

Во множество заключительных состояний войдут состояния, содержащие заключительное состояние 3 автомата M1:

F^A={{3},{0,3}, {1,3}, {0,1,3}, {0,2,3},{1,2,3}, {0,1,2, 3}}.

Функция переходов $$\Phi ^{A}$$ определена в следующей таблице

На самом деле нас интересуют лишь те состояния, в которые можно попасть из начального состояния {0}. Несложный анализ показывает, что их только три: {0,1}, {0,2 } и {0, 1, 3 }. Остальные состояния не достижимы из {0} и, следовательно, не влияют на работу автомата A. Их можно отбросить. Таким образом, в диаграмме автомата остаются 4 состояния, показанные на рис. 4.5.

Замечание. В рассмотренном примере у построенного ДКА A оказалось не больше состояний, чем у исходного НКА N1. К сожалению, это не всегда так. Существуют примеры НКА с n состояниями, для которых эквивалентные ДКА содержат не менее 2n состояний.

Задачи

Задача 4.1. Автомат по продаже кофе имеет щель для получения монет, кнопку, нажатие которой после уплаты достаточной суммы приводит к получению кофе, и накопитель, через который он выдает сдачу покупателю. Автомат принимает монеты достоинством в 1, 2 и 5 рублей. Чашка кофе стоит 8 руб. Пока полученная сумма недостаточна, горит красная лампочка. Если сумма, полученная автоматом, >= 8, то зажигается зеленая лампочка и после нажатия кнопки автомат наливает кофе и, если требуется, дает сдачу. Если автомат получает монету, когда горит зеленая лампочка, то он немедленно ее возвращает. Определите входной и выходной алфавиты конечного автомата, управляющего продажей кофе, и постройте его функции переходов и выходов.

Задача 4.2. Электронные часы имеют табло с указанием часов, минут и секунд и две управляющие кнопки. Одна кнопка переводит часы из нормального режима в режим настройки времени - вначале в настройку часов, затем - минут, затем - секунд, а затем возвращает в нормальный режим. Другая кнопка в нормальном режиме ничего не меняет, а в режиме настройки нажатие на нее увеличивает на единицу число настраеваемых часов, минут или секунд. Постройте автомат, который принимает на вход сигналы нажатия от двух кнопок, а на выходе выдает сигналы изменения режима и увеличения соответствующего числа.

Задача 4.3. Докажите лемму 4.1 индукцией по длине входного слова.

Задача 4.4. Постройте детерминированные конечные автоматы, которые распознают следующие языки в алфавите $$\sigma =\{ a, b\}$$:

Задача 4.5. Выше в примере 4.1 был построен автомат с выходом, выполняющий сложение двух двоичных чисел. Постройте автомат-распознаватель, который проверяет правильность сложения. На вход поступают последовательности троек нулей и единиц:

Автомат должен допустить такую последовательность, если y = y(n) ... y(2)y(1) - это первые n битов суммы двоичных чисел x1= x1(n)... x1(2)x1(1) и x2 = x2(n)... x2(2)x2(1).

Задача 4.7. Докажите лемму 4.2.

Задача 4.8. Докажите, что приведенный на рис. 4.5 автомат A распознает язык, состоящий из всех слов, заканчивающихся на 'aba'.

Задача 4.9. Используя процедуру детерминизации недетерминированных автоматов из теоремы 4.2, постройте ДКА, эквивалентный заданному НКА M.