Изменения
→Автоматные языки
|id=допускает
|definition=
Будем говорить, что автомат '''допускает''' (англ. ''accept'') слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.
}}
'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' (также '''''тупиковое состояние''''', '''''сток'''''), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».
== Способы представления ==
<tex>M = (Q, \Sigma , \bigcircdelta, q_0, F)</tex> — нетерминальное состояние,где*<tex>Q = {S_1, S_2}<br/tex>,*<tex>\circledcircSigma = \{0, 1 \}</tex> — терминальное состояние.,*<tex>q_0 = S_1<br/tex>Стрелка ,*<tex>\downarrowF = {S_1}</tex> указывает на начальное состояние., *<tex>\delta</smalltex>{{---}} функция переходов, представленная таблицей::{|class="wikitable" border="1" style="backgroundborder-collapse:#ffffffcollapse"! !! <center><tex>0</tex></center> !! <center><tex>1</tex></center>|а)[[Файл:Finite state machine 1.png-!<tex>S_1</tex> |150 px]]<tex>S_2</tex> б)[[Файл:Finite state machine 2.png|200 px]]<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>
|}
{{Определение
|definition=
Автоматы называются '''изоморфными''' (англ. ''isomorphic''), если существует [[wikipedia:Биекция Отображения | биекция]] между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, начальные {{---}} начальным
}}
{{Задача
=== Алгоритм ===
=== Псевдокод ===
* <tex>\mathtt {Transitions} </tex> {{---}} множество пар <tex>\langle a</tex>, <tex>T \rangle</tex> , где <tex> a \in \Sigma</tex>, <tex>T \in Q</tex> '''boolean''' dfs(Vertex u, Vertex v) visited1[u] = : ''true'Vertex' visited2[v] = ''true'' '''if''' (, v.transitions.size : '''!=Vertex''' u.transitions.size) : visited[u] = '''return''' ''falsetrue'' <font color="green">// заметим, что достаточно только одного массива <tex>\mathtt{visited}</tex> на два автомата</font> '''if''' (v.terminal != u.terminal) '''return!=''' ''false'' '''for''' (Transition e : u.transitionsterminal) '''char''' symbol = e.getSymbol() '''if''' ('''not''' v.transitions.existTransition(symbol)) '''return''' ''false''
'''boolean''' result = ''true''
'''for''' (Transition t <tex>\langle c, q \rangle</tex> : u.transitions) '''charVertex''' symbol = t.getSymbol() Vertex t1 = u.transitions.getVertex(symbolc) '''Vertex ''' t2 = v.transitions.getVertex(symbolc) '''if''' (visited1[одна из вершин t1] ', t2 ''!=дьявольская''' visited2[t2]) , а другая {{---}} нет
'''return''' ''false''
'''if''' (!visited1'''not''' visited[t1] && !visited2[t2]) result = result '''and''' dfs(t1, t2)
'''return''' result
== См. также ==
* [[Недетерминированные конечные автоматы]]
* [[Автомат для поиска образца в текстеКнута-Морриса-Пратта]]* [[Суффиксный автомат]]
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
