Изменения

'''Детерминированный конечный автомат (ДКА)''' (англ. ''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>p</tex>. Изначально автомат находится в стартовом состоянии <tex>s</tex>. Автомат считывает символы по очереди. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.

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

'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' (также '''''тупиковое состояние''''', '''''сток'''''), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину». == Способы представления =====Диаграмма переходов=== Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.:<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"|}

=== Примеры Таблица переходов=== Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>. <tex>M = (Q, \Sigma , \delta, q_0, F)</tex>, где*<tex>Q = {| borderS_1, S_2}</tex>,*<tex>\Sigma ="\{0, 1" cellpadding\}</tex>,*<tex>q_0 = S_1</tex>,*<tex>F = {S_1}</tex>, *<tex>\delta</tex> {{---}} функция переходов, представленная таблицей::{| class="5wikitable" cellspacingborder="01" style="textborder-aligncollapse:collapse"! !! <center><tex>0</tex></center> !! <center><tex>1</tex></center" width=60%>|style="background:#ffffff"|Автомат, принимающий строки из чередующихся символов ''a'' и ''b''-!<smalltex>S_1<br/tex>а)без «дьявольской вершины» | <br/tex>б)с «дьявольской вершиной» (отмечена серым цветом)S_2</smalltex>|style="background:#ffffff"|[[Файл:Consp dka.png|300 px]]<tex>S_1</tex>

|style="background:#ffffff"|[[Автомат для поиска образца в тексте]] для строки ''ababb''!<tex>S_2</tex> |style="background:#ffffff"|<div style="overflow:hidden;"tex>S_1<div style="margin:-80px 0px -90px 0px;"/tex>[[Файл:Automata.jpg|340px]]</divtex>S_2</divtex>

'''Мгновенное описание ''' ('''конфигурация''') (англ. ''snapshot'') {{- --}} пара <tex>\langle q , α\alpha \rangle</tex>, где <tex>q – </tex> {{---}} текущее состояние, α – <tex>\alpha</tex> {{---}} оставшиеся символы.

1.Переход за 1 шаг:{{Лемма|statement=* <tex>\langle q, \alpha \rangle \vdash ^* \langle p, \beta varepsilon \rangle</tex>, если:** <tex>\alpha = clangle p, \beta</tex>*\rangle \vdash^* <tex>\delta (qlangle r, c)=p </tex>2.Переход за 0 или более шагов:* <tex>\varepsilon \rangle \Rightarrow \langle q, \alpha \beta \rangle \vdash^* \langle pr, \beta varepsilon \rangle</tex>, если <tex>\exists n</tex>:.|proof=** <tex>\langle q, c_1 c_2 c_3 ...c_n\alpha\beta \rangle \vdash ^* \langle u_1p, c_2 c_3 ...c_n\beta \rangle \vdash ^* \langle u_2r, c_3 ...c_n\beta varepsilon \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>}}

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

Автомат== Изоморфизм двух автоматов =={{Определение|definition=Автоматы называются '''изоморфными''' (англ. ''isomorphic''), если существует [[Отображения | биекция]] между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, а начальные {{---}} начальным.}}{{Задача|definition= Задано два детерминированных конечных автомата. Определить, допускающий слова над алфавитом из символов a и bизоморфны ли они друг другу.Гарантируется, допускающий слова в которых перед каждым символом b идёт символ aчто все состояния автоматов достижимы.}}

=== Алгоритм ===Из определения следует, что если автоматы изоморфны, то можно их состояния занумеровать одним способом так, что вершины из разных автоматов с одинаковыми номерами будут равны — то есть в каждом из этих двух состояний существует переход в какое-то состояние с таким же номером, что и переход по этой же букве в другом состоянии. Поэтому мы можем зафиксировать какую-то нумерацию, например, в порядке [[Обход в глубину, цвета вершин | обхода в глубину]] по символам в лексикографическом порядке и просто проверить состояния с одинаковыми номерами на равенство. Если все состояния будут равны, то автоматы будут равны, в нашем случае будет следовать изоморфизм двух автоматов. Асимптотика алгоритма совпадает с асимптотикой обхода в глубину, то есть <tex>O(a|abN + 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> :DKA_2u.transitions) '''Vertex''' t1 = u.transitions.jpggetVertex(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

{{Лемма|statement== Источники информации==<tex>\langle q, \alpha \rangle \vdash^* \langle p''Хопкрофт Д., \varepsilon \rangleМотвани Р., \langle pУльман Д.'' Введение в теорию автоматов, \beta \rangle \vdash^* \langle rязыков и вычислений, \varepsilon \rangle \Rightarrow \langle q2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>2002. — С. 61.— ISBN 5-8459-0261-4|proof=<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p''Lawson, \beta \rangle \vdash^* \langle r, \varepsilon \rangleMark V. (2004). Finite automata''.<Chapman and Hall/tex>CRC. ISBN 1-58488-255-7.* [[wikipedia:Deterministic finite automaton | Wikipedia {{---}}Deterministic finite automaton]]

== Способ хранения автомата ==[[Категория: Теория формальных языков]][[ФайлКатегория:save_DKA.jpgАвтоматы и регулярные языки]] В ячейке таблицы (i, c) храним номер состояния, в которое можно перейти из состояния i по символу c. В массиве T отмечены допускающие состояния. Таким образом требуется O(|Q||Σ|) памяти.