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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Детерминированный конечный автомат (ДКА)''' (англ. ''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>\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> — функция переходов.
 
}}
 
}}
  
Строка 7: Строка 7:
 
Изначально автомат находится в стартовом состоянии <tex>s</tex>. Автомат считывает символы по очереди. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.
 
Изначально автомат находится в стартовом состоянии <tex>s</tex>. Автомат считывает символы по очереди. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.
 
{{Определение
 
{{Определение
|id=допускает
 
 
|definition=
 
|definition=
Будем говорить, что автомат '''допускает''' (англ. ''accept'') слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.
+
Будем говорить, что автомат '''допускает''' слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.
 
}}
 
}}
'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' (также '''''тупиковое состояние''''', '''''сток'''''), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».
+
'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''', из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».
  
 
== Способы представления ==
 
== Способы представления ==
===Диаграмма переходов===
+
* Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.
 +
* Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>.
  
Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.
+
== Примеры ==
:<tex>\bigcirc</tex> — нетерминальное состояние,
+
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=60%
:<tex>\circledcirc</tex> — терминальное состояние,
+
|style="background:#ffffff"|Автомат, принимающий непустые строки из чередующихся символов ''a'' и ''b'',<br/>
:Стрелка <tex>\downarrow</tex> указывает на начальное состояние.
+
<small>а) без «дьявольской вершины», <br/>б) с «дьявольской вершиной» (отмечена серым цветом).
{| 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"
 
|}
 
 
 
===Таблица переходов===
 
 
 
Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>.
 
  
<tex>M = (Q, \Sigma , \delta, q_0, F)</tex>, где
+
<tex>\bigcirc</tex> — нетерминальное состояние,
*<tex>Q = {S_1, S_2}</tex>,
+
<br/><tex>\circledcirc</tex> — терминальное состояние.
*<tex>\Sigma = \{0, 1 \}</tex>,
+
<br/>Стрелка <tex>\downarrow</tex> указывает на начальное состояние.</small>
*<tex>q_0 = S_1</tex>,
+
|style="background:#ffffff"|[[Файл:Consp dka.png|300 px]]
*<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>
+
|style="background:#ffffff"|[[Автомат для поиска образца в тексте]] для строки ''abbab''.
| <tex>S_1</tex>
+
|style="background:#ffffff"|[[Файл:Automata_Search.png|340px]]
| <tex>S_2</tex>
 
 
|}
 
|}
  
Строка 59: Строка 33:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Мгновенное описание''' ('''конфигурация''') (англ. ''snapshot'') {{---}} пара <tex>\langle q, \alpha \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</tex> {{---}} оставшиеся символы.
+
'''Мгновенное описание (конфигурация)''' {{---}} пара <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>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за 1 шаг <tex>(\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)</tex>, если:
 
* <tex>\alpha = c\beta</tex>,
 
* <tex>\alpha = c\beta</tex>,
 
* <tex>\delta (q, c)=p </tex>.
 
* <tex>\delta (q, c)=p </tex>.
Строка 78: Строка 52:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Множество <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>.
+
Множество <tex>L(\mathcal{A})=\{\alpha| \exists t \in T : \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle\}</tex> называется '''языком автомата <tex>\mathcal{A}</tex>'''.
 
}}
 
}}
 
Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.
 
Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.
Строка 84: Строка 58:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Множество языков всех ДКА образует множество '''автоматных языков''' <tex>\mathrm{AUT}</tex>.
+
Множество языков всех ДКА образует множество '''автоматных языков''' <tex>Aut</tex>.
}}
 
 
 
== Изоморфизм двух автоматов ==
 
{{Определение
 
|definition=
 
Автоматы называются '''изоморфными''' (англ. ''isomorphic''), если существует [[Отображения | биекция]] между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, а начальные {{---}} начальным.
 
}}
 
{{Задача
 
|definition=
 
Задано два детерминированных конечных автомата. Определить, изоморфны ли они друг другу.
 
Гарантируется, что все состояния автоматов достижимы.
 
 
}}
 
}}
  
=== Алгоритм ===
+
= См. также =
Из определения следует, что если автоматы изоморфны, то можно их состояния занумеровать одним способом так, что вершины из разных автоматов с одинаковыми номерами будут равны — то есть в каждом из этих двух состояний существует переход в какое-то состояние с таким же номером, что и переход по этой же букве в другом состоянии. Поэтому мы можем зафиксировать какую-то нумерацию, например, в порядке [[Обход в глубину, цвета вершин | обхода в глубину]] по символам в лексикографическом порядке и просто проверить состояния с одинаковыми номерами на равенство. Если все состояния будут равны, то автоматы будут равны, в нашем случае будет следовать изоморфизм двух автоматов. Асимптотика алгоритма совпадает с асимптотикой обхода в глубину, то есть <tex>O(N + M) </tex>, где <tex> N</tex> {{---}} суммарное число вершин в автоматах, <tex> M</tex> {{---}} суммарное число ребер.
 
 
 
=== Псевдокод ===
 
* <tex> \mathtt {Transitions} </tex> {{---}} множество пар  <tex>\langle a</tex>, <tex>T \rangle</tex> , где <tex> a \in \Sigma</tex>, <tex>T \in Q</tex>
 
* <tex> \mathtt {Assotiations} </tex> {{---}} массив, где каждому состоянию первого автомата соответствует найденное состояние второго автомата.
 
'''boolean''' dfs(u: '''Vertex''', v: '''Vertex'''):
 
    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
 
 
 
== См. также ==
 
 
* [[Недетерминированные конечные автоматы]]
 
* [[Недетерминированные конечные автоматы]]
* [[Автомат Кнута-Морриса-Пратта]]
+
* [[Автомат для поиска образца в тексте]]
* [[Суффиксный автомат]]
 
 
* [[Алгоритм Ахо-Корасик]]
 
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
 
  
== Источники информации==
+
= Литература =
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 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]]
 
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)