Изменения

'''Детерминированный конечный автомат (ДКА)''' — набор из пяти элементов <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 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>