Детерминированные конечные автоматы

Основные понятия

Определение:

Детерминированный конечный автомат (ДКА) — набор из пяти элементов [math]\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle[/math], где [math]\Sigma[/math] — алфавит, [math]Q[/math] — множество состояний автомата, [math]s[/math] — начальное состояние автомата, [math]T[/math] — множество допускающих состояний автомата, [math]\delta[/math] — функция переходов.

Процесс допуска

Опишем процесс допуска автоматом слова [math]p[/math]. Изначально автомат находится в стартовом состоянии [math]s[/math]. При считывании очередного символа [math]p_i[/math] автомат переходит в состояние [math]\delta(q, p_i)[/math], где [math]q[/math] — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.

Определение:

Будем говорить, что автомат допускает слово, если после окончания описанного выше процесса с этим словом автомат окажется в допускающем состоянии.

Замечание. Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную «дьявольскую вершину», из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».

Примеры

Автомат, принимающий строки из чередующихся символов a и b а)без «дьявольской вершины» б)с «дьявольской вершиной» (отмечена серым цветом)
Автомат для поиска образца в тексте для строки ababb

Обозначения

Определение:

Мгновенное описание (конфигурация) - , где q – текущее состояние, α – оставшиеся символы.</td></tr> </table> Для удобства можно ввести следующие обозначения: 1.Переход за 1 шаг: [math]\langle q, \alpha \rangle \vdash \langle p, \beta \rangle[/math], если: [math]\alpha = c\beta[/math] [math]\delta (q, c)=p [/math] 2.Переход за 0 или более шагов: [math]\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle[/math], если [math]\exists n[/math]: [math]\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle[/math] Автоматные языки Определение: [math]L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}[/math] --- язык автомата [math]\mathcal{A}[/math]. Пример: Автомат, допускающий слова над алфавитом из символов a и b, допускающий слова в которых перед каждым символом b идёт символ a. (a|ab)* Лемма: [math]\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle[/math] Доказательство: [math]\triangleright[/math] [math]\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.[/math] [math]\triangleleft[/math] Способ хранения автомата В ячейке таблицы (i, c) храним номер состояния, в которое можно перейти из состояния i по символу c. В массиве T отмечены допускающие состояния. Таким образом требуется O(|Q||Σ|) памяти.