Детерминированные конечные автоматы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Процесс допуска)
м (rollbackEdits.php mass rollback)
 
(не показано 155 промежуточных версий 21 участника)
Строка 1: Строка 1:
[[Категория: Теория формальных языков]]
 
== Детерминированный конечный автомат ==
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Детерминированный конечный автомат(ДКА) --- набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> -- алфавит, <tex>Q</tex> -- множество состояний автомата, <tex>s</tex> -- начальное состояние автомата, <tex>T</tex> -- Множество допускающих состояний автомата, <tex>\delta</tex> -- функция переходов.
+
'''Детерминированный конечный автомат (ДКА)''' (англ. ''deterministic finite automaton (DFA)'') — набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> алфавит (англ. ''alphabet''), <tex>Q</tex> множество состояний (англ. ''finite set of states''), <tex>s</tex> начальное (стартовое) состояние (англ. ''start state''), <tex>T</tex> — множество допускающих состояний (англ. ''set of accept states''), <tex>\delta</tex> функция переходов (англ. ''transition function'').
 +
}}
 +
 
 +
== Процесс допуска ==
 +
Изначально автомат находится в стартовом состоянии <tex>s</tex>. Автомат считывает символы по очереди. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.
 +
{{Определение
 +
|id=допускает
 +
|definition=
 +
Будем говорить, что автомат '''допускает''' (англ. ''accept'') слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.
 
}}
 
}}
 +
'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' (также '''''тупиковое состояние''''', '''''сток'''''), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».
  
Пример :
+
== Способы представления ==
 +
===Диаграмма переходов===
  
[[Файл:DKA_1.jpg‎]]
+
Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.
 +
:<tex>\bigcirc</tex> — нетерминальное состояние,
 +
:<tex>\circledcirc</tex> — терминальное состояние,
 +
:Стрелка <tex>\downarrow</tex> указывает на начальное состояние.
 +
{| class = "wikitable"
 +
!Пример!!Описание
 +
|-align="center"
 +
| style="background-color:white;" | [[Файл:Automata_Search.png|340px]]
 +
|Автомат для поиска образца в тексте для строки <tex>abbab</tex>.
 +
|-align="center"
 +
| style="background-color:white;" | [[Файл:Finite state machine 1.png|250 px]]
 +
|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b</tex>,без «дьявольской вершины».
 +
|-align="center"
 +
| style="background-color:white;" | [[Файл:Finite state machine 2.png|200 px]]
 +
|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b</tex>,  с «дьявольской вершиной».
 +
|-align="center"
 +
|}
  
q - начальное состояние.
+
===Таблица переходов===
r - допускающее состояние.
 
  
=== Процесс допуска ===
+
Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>.
Процесс допуска слова автоматом выглядит так:
 
* Изначально автомат находится в стартовом состоянии
 
* Ему на вход подается строка
 
* Далее на каждом шаге автомат берет новый символ строки и совершает соответствующий переход в новое состояние, ''если для символа не задано никакого перехода из текущего состояния, то слово считается недопущенным ''
 
* Слово считается допущенным, если после того, как прочитаны все его символы, автомат оказался в допускающем состоянии.
 
  
== Обозначения ==
+
<tex>M = (Q, \Sigma , \delta, q_0, F)</tex>, где
 +
*<tex>Q = {S_1, S_2}</tex>,
 +
*<tex>\Sigma = \{0, 1 \}</tex>,
 +
*<tex>q_0 = S_1</tex>,
 +
*<tex>F = {S_1}</tex>,
 +
*<tex>\delta</tex> {{---}} функция переходов, представленная таблицей:
 +
:{| class="wikitable" border="1" style="border-collapse:collapse"
 +
! !! <center><tex>0</tex></center> !! <center><tex>1</tex></center>
 +
|-
 +
!<tex>S_1</tex>
 +
| <tex>S_2</tex>
 +
| <tex>S_1</tex>
 +
|-
 +
!<tex>S_2</tex>
 +
| <tex>S_1</tex>
 +
| <tex>S_2</tex>
 +
|}
  
 +
== Автоматные языки ==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Мгновенное описание (конфигурация) - <q , α>, где q текущее состояние, α – оставшиеся символы.
+
'''Мгновенное описание''' ('''конфигурация''') (англ. ''snapshot'') {{---}} пара <tex>\langle q, \alpha \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</tex> {{---}} оставшиеся символы.
 
}}
 
}}
 +
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за один шаг <tex>(\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)</tex>, если:
 +
* <tex>\alpha = c\beta</tex>,
 +
* <tex>\delta (q, c)=p </tex>.
 +
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за конечное число шагов <tex>(\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle)</tex>, если <tex>\exists n:</tex>
 +
* <tex>\alpha = c_1 c_2 ... c_n\beta</tex>,
 +
* <tex>\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</tex>.
  
Для удобства можно ввести следующие обозначения:
 
  
1.Переход за 1 шаг:
+
{{Лемма
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если:
+
|statement=
** <tex>\alpha = c\beta</tex>
+
<tex>\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</tex>.
** <tex>\delta (q, c)=p </tex>
+
|proof=
2.Переход за 0 или более шагов:
+
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если <tex>\exists n</tex>:
+
}}
** <tex>\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</tex>
 
  
=== Автоматные языки ===
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> --- язык автомата <tex>\mathcal{A}</tex>.
+
Множество <tex>L(\mathcal{A})=\{\alpha \mid \exists t \in T : \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle\}</tex> называется '''языком автомата''' (англ. ''automata's language'') <tex>\mathcal{A}</tex>.
 
}}
 
}}
 +
Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.
  
Пример:
+
{{Определение
 +
|definition=
 +
Множество языков всех ДКА образует множество '''автоматных языков''' <tex>\mathrm{AUT}</tex>.
 +
}}
  
Автомат, допускающий слова над алфавитом из символов a и b, допускающий слова в которых перед каждым символом b идёт символ a.
+
== Изоморфизм двух автоматов ==
 
+
{{Определение
(a|ab)*
+
|definition=
 
+
Автоматы называются '''изоморфными''' (англ. ''isomorphic''), если существует [[Отображения | биекция]] между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, а начальные {{---}} начальным.
[[Файл:DKA_2.jpg]]
+
}}
 +
{{Задача
 +
|definition=
 +
Задано два детерминированных конечных автомата. Определить, изоморфны ли они друг другу.
 +
Гарантируется, что все состояния автоматов достижимы.
 +
}}
  
 +
=== Алгоритм ===
 +
Из определения следует, что если автоматы изоморфны, то можно их состояния занумеровать одним способом так, что вершины из разных автоматов с одинаковыми номерами будут равны — то есть в каждом из этих двух состояний существует переход в какое-то состояние с таким же номером, что и переход по этой же букве в другом состоянии. Поэтому мы можем зафиксировать какую-то нумерацию, например, в порядке [[Обход в глубину, цвета вершин | обхода в глубину]] по символам в лексикографическом порядке и просто проверить состояния с одинаковыми номерами на равенство. Если все состояния будут равны, то автоматы будут равны, в нашем случае будет следовать изоморфизм двух автоматов. Асимптотика алгоритма совпадает с асимптотикой обхода в глубину, то есть <tex>O(N + M) </tex>, где <tex> N</tex> {{---}} суммарное число вершин в автоматах, <tex> M</tex> {{---}} суммарное число ребер.
  
{{Лемма
+
=== Псевдокод ===
|statement=
+
* <tex> \mathtt {Transitions} </tex> {{---}} множество пар  <tex>\langle a</tex>, <tex>T \rangle</tex> , где <tex> a \in \Sigma</tex>, <tex>T \in Q</tex>
<tex>\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</tex>
+
* <tex> \mathtt {Assotiations} </tex> {{---}} массив, где каждому состоянию первого автомата соответствует найденное состояние второго автомата.
|proof=
+
'''boolean''' dfs(u: '''Vertex''', v: '''Vertex'''):
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
+
    visited[u] = ''true''  <font color="green">// заметим, что достаточно только одного массива <tex>\mathtt{visited}</tex> на два автомата</font>
}}
+
   
 +
    '''if''' (v.terminal '''!=''' u.terminal)
 +
      '''return''' ''false'' 
 +
    associations[u] = v
 +
    '''boolean''' result = ''true''
 +
    '''for''' (<tex>\langle c, q \rangle</tex> : u.transitions)     
 +
      '''Vertex''' t1 = u.transitions.getVertex(c)
 +
      '''Vertex''' t2 = v.transitions.getVertex(c)
 +
      '''if''' одна из вершин t1, t2 ''дьявольская'', а другая {{---}} нет
 +
        '''return''' ''false''
 +
      '''if''' (visited[t1])
 +
        result = result '''and''' t2 '''==''' associations[t1]
 +
      '''else'''
 +
        result = result '''and''' dfs(t1, t2)               
 +
         
 +
    '''return''' result
  
== Способ хранения автомата ==
+
== См. также ==
 +
* [[Недетерминированные конечные автоматы]]
 +
* [[Автомат Кнута-Морриса-Пратта]]
 +
* [[Суффиксный автомат]]
 +
* [[Алгоритм Ахо-Корасик]]
 +
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
  
[[Файл:save_DKA.jpg]]
+
== Источники информации==
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 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 | Wikipedia {{---}} Deterministic finite automaton]]
  
В ячейке таблицы (i, c) храним номер состояния, в которое можно перейти из состояния i по символу c. В массиве T отмечены допускающие состояния. Таким образом требуется O(|Q||Σ|) памяти.
+
[[Категория: Теория формальных языков]]
 +
[[Категория: Автоматы и регулярные языки]]

Текущая версия на 19:20, 4 сентября 2022

Определение:
Детерминированный конечный автомат (ДКА) (англ. 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]\bigcirc[/math] — нетерминальное состояние,
[math]\circledcirc[/math] — терминальное состояние,
Стрелка [math]\downarrow[/math] указывает на начальное состояние.
Пример Описание
Automata Search.png Автомат для поиска образца в тексте для строки [math]abbab[/math].
Finite state machine 1.png Автомат, принимающий непустые строки из чередующихся символов [math]a[/math] и [math]b[/math],без «дьявольской вершины».
Finite state machine 2.png Автомат, принимающий непустые строки из чередующихся символов [math]a[/math] и [math]b[/math], с «дьявольской вершиной».

Таблица переходов

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

[math]M = (Q, \Sigma , \delta, q_0, F)[/math], где

  • [math]Q = {S_1, S_2}[/math],
  • [math]\Sigma = \{0, 1 \}[/math],
  • [math]q_0 = S_1[/math],
  • [math]F = {S_1}[/math],
  • [math]\delta[/math] — функция переходов, представленная таблицей:
[math]0[/math]
[math]1[/math]
[math]S_1[/math] [math]S_2[/math] [math]S_1[/math]
[math]S_2[/math] [math]S_1[/math] [math]S_2[/math]

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

Определение:
Мгновенное описание (конфигурация) (англ. 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]
  • [math] \mathtt {Assotiations} [/math] — массив, где каждому состоянию первого автомата соответствует найденное состояние второго автомата.
boolean dfs(u: Vertex, v: Vertex): 
   visited[u] = true   // заметим, что достаточно только одного массива [math]\mathtt{visited}[/math] на два автомата
   
   if (v.terminal != u.terminal)
     return false   
   associations[u] = v
   boolean result = true
   for ([math]\langle c, q \rangle[/math] : u.transitions)      
     Vertex t1 = u.transitions.getVertex(c)
     Vertex t2 = v.transitions.getVertex(c)
     if одна из вершин t1, t2 дьявольская, а другая — нет
       return false
     if (visited[t1]) 
       result = result and t2 == associations[t1]
     else
       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