Изменения
Нет описания правки
|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>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если
** <tex>\alpha = c\beta</tex>
** <tex>\delta (q, c)=p </tex>
* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</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 \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \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>.
}}
