Изменения

== Детерминированный конечный автомат Основные понятия ==

'''Детерминированный конечный автомат(ДКА) --- ''' — набор из пяти элементов <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=Будем говорить, что автомат '''допускает''' слово, если для символа не задано никакого перехода после окончания описанного выше процесса с этим словом автомат окажется в допускающем состоянии.}}'''Замечание.''' Если в какой-то момент из текущего состояниянет перехода по считанному символу, то будем считать, что автомат не допускает данное слово считается недопущенным . При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' * Слово считается допущенным, если после тогоиз которой любой переход ведет в неё же саму, как прочитаны и заменить все его символы, автомат оказался несуществующие переходы на переходы в допускающем состоянии«дьявольскую вершину».