Изменения
Нет описания правки
!Пример!!Описание
|-align="center"
| style="background-color:white;" |[[Файл:Automata_Search.png|340px]]
|Автомат для поиска образца в тексте для строки <tex>abbab</tex>.
|-align="center"
| style="background-color:white;" |[[Файл:Finite state machine 1.png|350 250 px]]
|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b</tex>,без «дьявольской вершины».
|-align="center"
| style="background-color:white;" |[[Файл:Finite state machine 2.png|350 200 px]]
|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b</tex>, с «дьявольской вершиной».
|-align="center"
*<tex>F = {S_1}</tex>,
*<tex>\delta</tex> {{---}} функция переходов, представленная таблицей:
:{| borderclass="1wikitable" cellpaddingborder="1" cellspacingstyle="0border-collapse:collapse"| || ! !! <center><tex>0</tex></center> || !! <center><tex>1</tex></center>
|-
|-
|}
{{Определение
|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'''):
visited[u] = ''true'' <font color="green">// заметим, что достаточно только одного массива <tex>\mathtt{visited}</tex> на два автомата</font>
'''if''' (v.terminal '''!=''' u.terminal)
'''return''' ''false''
'''boolean''' result = ''true''
'''for''' (<tex>\langle c, q \rangle</tex> : u.transitions)
'''if''' одна из вершин t1, t2 ''дьявольская'', а другая {{---}} нет
'''return''' ''false''
'''if''' (visited[t1]) result = result '''and'not''t2 ' visited''==''' associations[t1]) '''else'''
result = result '''and''' dfs(t1, t2)
== См. также ==
* [[Недетерминированные конечные автоматы]]
* [[Автомат для поиска образца в текстеКнута-Морриса-Пратта]]* [[Суффиксный автомат]]
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
