1632
правки
Изменения
м
* ===Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.* Таблица переходов <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<br/tex>б) и <tex>b</tex>, с «дьявольской вершиной» (отмечена серым цветом).|-align="center"|}
Будем проверять множества переходов для Из определения следует, что если автоматы изоморфны, то можно их состояния занумеровать одним способом так, что вершины из разных автоматов с одинаковыми номерами будут равны — то есть в каждом из этих двух вершинсостояний существует переход в какое-то состояние с таким же номером, что и переход по этой же букве в другом состоянии. Запустим Поэтому мы можем зафиксировать какую-то нумерацию, например, в порядке [[Обход в глубину, цвета вершин | обход обхода в глубину]] из стартовых вершин, если множество переходов по ребрам для двух вершин совпадают символам в лексикографическом порядке и также это выполнено для вершин соответствующим концам ребер (если у нас соответствующие вершины дьявольскиепросто проверить состояния с одинаковыми номерами на равенство. Если все состояния будут равны, то множество переходов считаем равными) то два автомата изоморфныавтоматы будут равны, в нашем случае будет следовать изоморфизм двух автоматов. Этот алгоритм пройдет по всем вершинам и ребрам ровно один разАсимптотика алгоритма совпадает с асимптотикой обхода в глубину, из этого следует время работы то есть <tex>O(N + M) </tex>, где <tex> N</tex> {{---}} суммарное число вершин в автоматах, <tex> M</tex> {{---}} суммарное число ребер.
Будет класс * <tex>Vertex\mathtt {Transitions} </tex> {{---}} множество пар <tex>\langle a</tex>, в котором будем хранить все переходы из одной вершины (<tex>transitionsT \rangle</tex>), соответственно мы можем получить получить вершину на другом концегде <tex> a \in \Sigma</tex>, переход (метод <tex> getT \in Q</tex> * <tex> \mathtt {Assotiations} </tex>){{---}} массив, где каждому состоянию первого автомата соответствует найденное состояние второго автомата. '''boolean''' dfs(Vertex u, Vertex v) : '''forVertex''' (Transition e , v: u.transitions) '''if''' ('''notVertex''' v.transitions.contains(e)) : visited[u] = ''true'return''' ''false'' <font color="green">// заметим, что достаточно только одного массива <tex>\mathtt{visited}</tex> на два автомата</font>
rollbackEdits.php mass rollback
|id=допускает
|definition=
Будем говорить, что автомат '''допускает''' (англ. ''accept'') слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.
}}
'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' (также '''''тупиковое состояние''''', '''''сток'''''), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».
== Способы представления ==
===Таблица переходов=== Таблица переходов <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>
|}
{{Определение
|definition=
'''Мгновенное описание''' ('''конфигурация''') (англ. ''snapshot'') {{---}} пара <tex>\langle q, \alpha \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</tex> {{---}} оставшиеся символы.
}}
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за один шаг <tex>(\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)</tex>, если:
{{Определение
|definition=
Множество <tex>L(\mathcal{A})=\{\alpha \mid \exists t \in T : \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle\}</tex> называется '''языком автомата ''' (англ. ''automata's language'') <tex>\mathcal{A}</tex>.
}}
Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.
{{Определение
|definition=
Автоматы называются '''изоморфными''' (англ. ''isomorphic''), если существует [[wikipedia:Биекция Отображения | биекция]] между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным, а начальные {{---}} начальным.
}}
{{Задача
=== Алгоритм ===
=== Псевдокод ===
'''if''' (v.transitions.size terminal '''!=''' u.transitions.sizeterminal) '''return''' ''false'' associations[u] = v
'''boolean''' result = ''true''
'''for''' (Transition t <tex>\langle c, q \rangle</tex> : u.transitions) '''Vertex ''' t1 = u.transitions.getgetVertex(tc) '''Vertex ''' t2 = v.transitions.getgetVertex(tc) '''if''' одна из вершин t1, t2 ''дьявольская'', а другая {{---}} нет '''return''' ''false'' '''if''' (visited[t1]) result = result '''and''' t2 '''==''' associations[t1] '''else''' result = result '''and''' dfs(t1, t2)
'''return''' result
== См. также ==
* [[Недетерминированные конечные автоматы]]
* [[Автомат для поиска образца в текстеКнута-Морриса-Пратта]]* [[Суффиксный автомат]]
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
