Бюрократы, editor, Администраторы
422
правки
Изменения
м
Нет описания правки
}}
=== Процесс допуска ===
Опишем процесс допуска автоматом слова <tex>p</tex>. Изначально автомат находится в стартовом состоянии <tex>s</tex>. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.
{{Определение
|definition=
Будем говорить, что автомат '''допускает''' слово, если после окончания описанного выше процесса с этим словом автомат окажется в допускающем состоянии.
}}
'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''', из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».
=== Примеры ===
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=60%
|style="background:#ffffff"|Автомат, принимающий непустые строки из чередующихся символов ''a'' и ''b'',<smallbr/><br/small>а)без «дьявольской вершины» , <br/>б)с «дьявольской вершиной» (отмечена серым цветом).<tex>\bigcirc</tex> — нетерминальное состояние,<br/><tex>\circledcirc</tex> — терминальное состояние.<br/>Стрелка <tex>\downarrow</tex> указывает на начальное состояние.</small>
|style="background:#ffffff"|[[Файл:Consp dka.png|300 px]]
|-
|style="background:#ffffff"|[[Автомат для поиска образца в тексте]] для строки ''abbab''.
|style="background:#ffffff"|<div style="overflow:hidden;">
<div style="margin:-80px 0px -90px 0px;">
}}
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за 1 шаг <tex>(\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)</tex>, если:
* <tex>\alpha = c\beta</tex>,* <tex>\delta (q, c)=p </tex>.
Будем говорить, что конфигурация <tex>\langle p, \beta \rangle</tex> выводима из <tex>\langle q, \alpha \rangle</tex> за конечное число шагов <tex>(\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle)</tex>, если <tex>\exists n:</tex>
* <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>.
{{Лемма
|statement=
<tex>\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>.
|proof=
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
