76
правок
Изменения
Нет описания правки
== Основные понятия ==
{{Определение
'''Детерминированный конечный автомат (ДКА)''' — набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> — алфавит, <tex>Q</tex> — множество состояний автомата, <tex>s</tex> — начальное состояние автомата, <tex>T</tex> — множество допускающих состояний автомата, <tex>\delta</tex> — функция переходов.
}}
=== Процесс допуска ===
Опишем процесс допуска автоматом слова <tex>p</tex>. Изначально автомат находится в стартовом состоянии <tex>s</tex>. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.
|}
{{Определение
|definition=
'''Мгновенное описание (конфигурация)''' — пара <tex>L(\mathcal{A})=\{\alpha| \langle sq, \alpha \rangle \vdash^* \langle t</tex>, \varepsilon \rangle t \in T\}где <tex>q</tex> --- язык автомата – текущее состояние, <tex>\mathcal{A}alpha</tex>– оставшиеся символы.
}}
{{Лемма
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
}}
{{Определение
|definition=
Множество <tex>L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> называется '''языком автомата <tex>\mathcal{A}</tex>'''. Множество языков всех автоматов образует множество '''автоматных языков''' <tex>Aut</tex>.
}}
== Способы представления автомата ==
* Диаграмма переходов — граф, в котором состояниям соответствуют вершины, а рёбрам — переходы между состояниям
* Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>.
== Способ хранения автомата См. также ==* [[Недетерминированные конечные автоматы]]* [[Автомат для поиска образца в тексте]]* [[Алгоритм Ахо-Корасик]]
