Изменения
→Автоматные языки
== Способы представления ==
Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.:<tex>\bigcirc</tex> — нетерминальное состояние,:<tex>\circledcirc</tex> — терминальное состояние,:Стрелка <tex>\downarrow</tex> указывает на начальное состояние.{| class ="wikitable" !Пример!!Описание|-align= Примеры "center"| style="background-color:white;" | [[Файл:Automata_Search.png|340px]]|Автомат для поиска образца в тексте для строки <tex>abbab</tex>.|-align="center"| style="background-color:white;" | [[Файл:Finite state machine 1.png|250 px]]|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b</tex>,без «дьявольской вершины». |-align="center"| style="background-color:white;" | [[Файл:Finite state machine 2.png|200 px]]|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b</tex>, с «дьявольской вершиной». |-align="center"|}
===Представление диаграммой Таблица переходов===
<tex>M = (Q, \Sigma , \delta, q_0, F)</tex>, где
*<tex>Q = {S_1, S_2}</tex>,
*<tex>\Sigma</tex> = \{0, 1\}</tex>,
*<tex>q_0 = S_1</tex>,
*<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>
|-
|-
|}
== См. также ==
* [[Недетерминированные конечные автоматы]]
* [[Автомат для поиска образца в текстеКнута-Морриса-Пратта]]* [[Суффиксный автомат]]
* [[Алгоритм Ахо-Корасик]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]