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

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

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

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

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

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

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

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

Способы представления

• Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.
• Таблица переходов [math]T (|Q| \times |\Sigma|)[/math], дающая табличное представление функции [math]\delta[/math].

Примеры

Автомат, принимающий непустые строки из чередующихся символов a и b, а) без «дьявольской вершины», б) с «дьявольской вершиной» (отмечена серым цветом). [math]\bigcirc[/math] — нетерминальное состояние, [math]\circledcirc[/math] — терминальное состояние. Стрелка [math]\downarrow[/math] указывает на начальное состояние.	а) б)
Автомат для поиска образца в тексте для строки abbab.

Автоматные языки

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

Мгновенное описание (конфигурация) (англ. snapshot) — пара [math]\langle q, \alpha \rangle[/math], где [math]q[/math] — текущее состояние, [math]\alpha[/math] — оставшиеся символы.

Будем говорить, что конфигурация [math]\langle p, \beta \rangle[/math] выводима из [math]\langle q, \alpha \rangle[/math] за один шаг [math](\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)[/math], если:

• [math]\alpha = c\beta[/math],
• [math]\delta (q, c)=p [/math].

Будем говорить, что конфигурация [math]\langle p, \beta \rangle[/math] выводима из [math]\langle q, \alpha \rangle[/math] за конечное число шагов [math](\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle)[/math], если [math]\exists n:[/math]

• [math]\alpha = c_1 c_2 ... c_n\beta[/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 ... \vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle[/math].

Лемма:

[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]

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

Множество [math]L(\mathcal{A})=\{\alpha \mid \exists t \in T : \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle\}[/math] называется языком автомата (англ. automata's language) [math]\mathcal{A}[/math].

Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.

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

Множество языков всех ДКА образует множество автоматных языков [math]\mathrm{AUT}[/math].

Изоморфизм двух автоматов

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

Автоматы называются изоморфными (англ. isomorphic), если существует биекция между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, начальные — начальным

Задача:

Задано два детерминированных конечных автомата. Определить, изоморфны ли они друг другу. Гарантируется, что все состояния автоматов достижимы.

Алгоритм

Будем проверять множества переходов для двух вершин. Запустим обход в глубину из стартовых вершин, если множество переходов по ребрам для двух вершин совпадают и также это выполнено для вершин соответствующим концам ребер (если у нас соответствующие вершины дьявольские, то множество переходов считаем равными) то два автомата изоморфны. Заметим, что если мы рассмотрим два автомата состоящих из пройденных вершин, то эти два автомата будут изоморфны (из этого следует, что на когда мы обойдем все вершины, это тоже будет выполнено). Этот алгоритм пройдет по всем вершинам и ребрам ровно один раз, из этого следует время работы [math]O(N + M) [/math], где [math] N[/math] — суммарное число вершин в автоматах, [math] M[/math] — суммарное число ребер.

Псевдокод

[math]\mathtt Transitions[/math] — множество пар [math]\langle a[/math], [math]T \rangle[/math] , где [math] a \in \Sigma[/math], [math]T \in Q[/math]

boolean dfs(Vertex u, Vertex v) 
   visited1[u] = true
   visited2[v] = true
   if (v.transitions.size != u.transitions.size) 
     return false
   if (v.terminal != u.terminal)
     return false 
       
   for (Transition e : u.transitions) 
     char symbol = e.getSymbol()
     if (not v.transitions.existTransition(symbol)) 
       return false   
     
   boolean result = true
   for (Transition t : u.transitions) 
     char symbol = t.getSymbol()
     Vertex t1 = u.transitions.getVertex(symbol)
     Vertex t2 = v.transitions.getVertex(symbol)
     if (visited1[t1] != visited2[t2])                
       return false
     if (!visited1[t1] && !visited2[t2]) 
       result =  result and dfs(t1, t2)                
         
   return result

См. также

• Недетерминированные конечные автоматы
• Автомат для поиска образца в тексте
• Алгоритм Ахо-Корасик
• Теорема Клини (совпадение классов автоматных и регулярных языков)

Источники информации

• Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7.
• Wikipedia — Deterministic finite automaton