Изменения

* ===Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.* Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>.===

== Примеры ==Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.:<tex>\bigcirc</tex> — нетерминальное состояние,:<tex>\circledcirc</tex> — терминальное состояние,:Стрелка <tex>\downarrow</tex> указывает на начальное состояние.{| borderclass ="1wikitable" cellpadding!Пример!!Описание|-align="5center" cellspacing| style="0background-color:white;" style| [[Файл:Automata_Search.png|340px]]|Автомат для поиска образца в тексте для строки <tex>abbab</tex>.|-align="text-align:center" width=60%|style="background-color:#ffffffwhite;"| [[Файл:Finite state machine 1.png|250 px]]|Автомат, принимающий непустые строки из чередующихся символов ''<tex>a'' </tex> и ''<tex>b'',<br/tex><small>а) ,без «дьявольской вершины». |-align="center"| style="background-color:white;" | [[Файл:Finite state machine 2.png|200 px]]|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b<br/tex>б) , с «дьявольской вершиной» . |-align="center"|} ===Таблица переходов=== Таблица переходов <tex>T (отмечена серым цветом|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>.

<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>

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

Из определения следует, что если автоматы изоморфны, то можно их состояния занумеровать одним способом так, что вершины из разных автоматов с одинаковыми номерами будут равны — то есть в каждом из этих двух состояний существует переход в какое-то состояние с таким же номером, что и переход по этой же букве в другом состоянии. Поэтому мы можем зафиксировать какую-то нумерацию, например, в порядке [[Обход в глубину, цвета вершин | обхода в глубину]] по символам в лексикографическом порядке и просто проверить состояния с одинаковыми номерами на равенство. Если все состояния будут равны , то автоматы будут равны, в нашем случае будет следовать изоморфизм двух автоматов. Этот алгоритм пройдет по всем вершинам и ребрам ровно 2 раза (нумерация вершин + проверка на равенство)Асимптотика алгоритма совпадает с асимптотикой обхода в глубину, из этого следует время работы то есть <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(Vertex u, Vertex v) visited1[u] = : ''true'' visited2[v] = Vertex''true'' '''if''' (, v.transitions.size : '''!=Vertex''' u.transitions.size) : visited[u] = '''return''' ''falsetrue'' <font color="green">// заметим, что достаточно только одного массива <tex>\mathtt{visited}</tex> на два автомата</font>

'''return''' ''false'' '''for''' (Transition e : associations[u.transitions) '''char''' symbol ] = e.getSymbol() '''if''' ('''not''' v.transitions.existTransition(symbol)) '''return''' ''false''

'''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]) , а другая {{---}} нет

'''if''' (!visited1visited[t1] && !visited2) result = result '''and''' t2 '''==''' associations[t2t1]) '''else''' result = result '''and''' dfs(t1, t2)

* [[Автомат для поиска образца в текстеКнута-Морриса-Пратта]]* [[Суффиксный автомат]]