Изменения

'''Детерминированный конечный автомат(ДКА) --- ''' (англ. ''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'') слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.

Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.:<tex>\bigcirc</tex> — нетерминальное состояние,:<tex>\circledcirc</tex> — терминальное состояние,:Стрелка <tex>\downarrow</tex> указывает на начальное состояние.{| class = "wikitable" !Пример!!Описание|-align="center"| style="background-color:white;" | [[Файл:DKA_1Automata_Search.jpg‎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 = Обозначения {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>|}

'''Мгновенное описание ''' ('''конфигурация''') (англ. ''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''), если существует [[Отображения | биекция]] между их вершинами такая, что сохраняются все переходы, допускающий слова над алфавитом из символов a и bтерминальные состояния соответствуют терминальным, допускающий слова в которых перед каждым символом b идёт символ aа начальные {{---}} начальным.}}{{Задача(a|ab)*definition= Задано два детерминированных конечных автомата. Определить, изоморфны ли они друг другу.[[Файл:DKA_2Гарантируется, что все состояния автоматов достижимы.jpg]]}}

=== Псевдокод ===* <tex> \mathtt {Transitions} </tex> {{Лемма|statement=---}} множество пар <tex>\langle qa</tex>, \alpha <tex>T \rangle \vdash^* \langle p</tex> , где <tex> a \varepsilon in \rangleSigma</tex>, <tex>T \langle p, \beta \rangle \vdash^in Q</tex> * <tex> \langle rmathtt {Assotiations} </tex> {{---}} массив, \varepsilon \rangle \Rightarrow \langle qгде каждому состоянию первого автомата соответствует найденное состояние второго автомата. '''boolean''' dfs(u: '''Vertex''', \alpha\beta \rangle \vdash^* \langle rv: '''Vertex'''): visited[u] = ''true'' <font color="green">// заметим, что достаточно только одного массива <tex>\varepsilon \ranglemathtt{visited}</tex>на два автомата</font> '''if''' (v.terminal '''!=''' u.terminal) '''return''' ''false'' associations[u] = v|proof '''boolean''' result =''true'' '''for''' (<tex>\langle c, q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \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* ''Lawson, Mark V. (2004). Finite automata''. Chapman and Hall/CRC. ISBN 1-58488-255-7.* [[Файлwikipedia:save_DKA.jpgDeterministic finite automaton | Wikipedia {{---}} Deterministic finite automaton]]