Изменения
→Автоматные языки
== Способы представления ==
===Таблица переходов=== Таблица переходов <tex>T (|Q| \times |\bigcircSigma|)</tex> — нетерминальное состояние,дающая табличное представление функции <tex>\delta</tex>. <brtex>M = (Q, \Sigma , \delta, q_0, F)</tex>, где*<tex>Q = {S_1, S_2}</tex>,*<tex>\Sigma = \{0, 1 \circledcirc}</tex> — терминальное состояние.,*<tex>q_0 = S_1<br/tex>Стрелка ,*<tex>\downarrowF = {S_1}</tex> указывает на начальное состояние., *<tex>\delta</smalltex>{{---}} функция переходов, представленная таблицей::{|class="wikitable" border="1" style="backgroundborder-collapse:#ffffffcollapse"|а)[[Файл:Finite state machine ! !! <center><tex>0</tex></center> !! <center><tex>1.png|150 px]]б)[[Файл:Finite state machine 2.png|200 px]]</tex></center>
|-
!<tex>S_1</tex> |style="background:#ffffff"<tex>S_2</tex> |[[Автомат для поиска образца в тексте]] для строки ''abbab''.<tex>S_1</tex>|style="background:#ffffff"-!<tex>S_2</tex> |[[Файл:Automata_Search.png<tex>S_1</tex> |340px]]<tex>S_2</tex>
|}
=== Алгоритм ===
Из определения следует, что если автоматы изоморфны, то можно их состояния занумеровать одним способом так, что вершины из разных автоматов с одинаковыми номерами будут равны — то есть в каждом из этих двух состояний существует переход в какое-то состояние с таким же номером, что и переход по этой же букве в другом состоянии. Поэтому мы можем зафиксировать какую-то нумерацию, например, в порядке [[Обход в глубину, цвета вершин | обхода в глубину]] по символам в лексикографическом порядке и просто проверить состояния с одинаковыми номерами на равенство. Если все состояния будут равны , то автоматы будут равны, в нашем случае будет следовать изоморфизм двух автоматов. Асимптотика алгоритма совпадает с асимптотикой обхода в глубину, то есть <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>
'''boolean''' dfs(u: '''Vertex''', v: '''Vertex'''):
'''if''' (v.terminal '''!=''' u.terminal)
'''boolean''' result = ''true''
'''Vertex''' t1 = u.transitions.getVertex(c)
'''Vertex''' t2 = v.transitions.getVertex(c)
'''if''' (visited1[одна из вершин t1] '', t2 '!='дьявольская'' visited2[t2]) , а другая {{---}} нет
'''return''' ''false''
'''if''' (!visited1'''not''' visited[t1] && !visited2[t2]) result = result '''and''' dfs(t1, t2)
'''return''' result
== См. также ==
* [[Недетерминированные конечные автоматы]]
* [[Автомат для поиска образца в текстеКнута-Морриса-Пратта]]* [[Суффиксный автомат]]
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]