Изменения

{{Определение

|definition=

'''Детерминированный конечный автомат (ДКА)''' — набор из пяти элементов <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>s</tex>. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.

{{Определение

'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''', из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».

{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=60%

|style="background:#ffffff"|Автомат, принимающий непустые строки из чередующихся символов ''a'' и ''b'',<br/>

<small>а) без «дьявольской вершины», <br/>б) с «дьявольской вершиной» (отмечена серым цветом).

<tex>\bigcirc</tex> — нетерминальное состояние,

<br/><tex>\circledcirc</tex> — терминальное состояние.

</div>

|}

== Автоматные языки ==

* <tex>\alpha = c_1 c_2 ... c_n\beta</tex>,

* <tex>\langle q, c_1 c_2 c_3 ... c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ... c_n\beta \rangle \vdash \langle u_2, c_3 ... c_n\beta \rangle \vdash ... \vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>.

{{Лемма

<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>

}}

{{Определение

|definition=

Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.

* [[Недетерминированные конечные автоматы]]

* [[Автомат для поиска образца в тексте]]

* [[Алгоритм Ахо-Корасик]]

* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]