Изменения
Нет описания правки
== Способы представления ==
Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.:<tex>\bigcirc</tex> — нетерминальное состояние,:<tex>\circledcirc</tex> — терминальное состояние,:Стрелка <tex>\downarrow</tex> указывает на начальное состояние.{| class == Примеры =="wikitable" !Пример!!Описание{| border-align="1center" cellpadding| style="5background-color:white;" cellspacing| [[Файл:Automata_Search.png|340px]]|Автомат для поиска образца в тексте для строки <tex>abbab</tex>.|-align="0center" | style="textbackground-color:white;" | [[Файл:Finite state machine 1.png|250 px]]|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b</tex>,без «дьявольской вершины». |-align:="center" width=60%|style="background-color:#ffffffwhite;"| [[Файл:Finite state machine 2.png|200 px]]|Автомат, принимающий непустые строки из чередующихся символов ''<tex>a'' </tex> и ''<tex>b'',<br/tex>, с «дьявольской вершиной». |-align="center"|} ===Таблица переходов=== Таблица переходов <smalltex>аT (|Q| \times |\Sigma|) без «дьявольской вершины»</tex>, дающая табличное представление функции <tex>\delta<br/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>
|}
{{Определение
|definition=
Автоматы называются '''изоморфными''' (англ. ''isomorphic''), если существует [[Отображения | биекция]] между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, а начальные {{---}} начальным.
}}
{{Задача
=== Псевдокод ===
* <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'''):
'''if''' (v.terminal '''!=''' u.terminal)
'''return''' ''false''
'''boolean''' result = ''true''
'''for''' (<tex>\langle c, q \rangle</tex> : u.transitions)
'''Vertex''' t1 = u.transitions.getVertex(c)
'''Vertex''' t2 = v.transitions.getVertex(c)
'''if''' (visited1[одна из вершин t1] '', t2 '!='дьявольская'' visited2[t2]) , а другая {{---}} нет
'''return''' ''false''
'''if''' (visited[t1]) result = result '''notand''' visited1t2 '''==''' associations[t1] '''and notelse''' visited2[t2])
result = result '''and''' dfs(t1, t2)
== См. также ==
* [[Недетерминированные конечные автоматы]]
* [[Автомат для поиска образца в текстеКнута-Морриса-Пратта]]* [[Суффиксный автомат]]
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
