Изменения

'''Детерминированный конечный автомат(ДКА) --- ''' (англ. ''deterministic finite automaton (DFA)'') — набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> -- — алфавит(англ. ''alphabet''), <tex>Q</tex> -- — множество состояний автомата(англ. ''finite set of states''), <tex>s</tex> -- — начальное (стартовое) состояние автомата(англ. ''start state''), <tex>T</tex> -- Множество — множество допускающих состояний автомата(англ. ''set of accept states''), <tex>\delta</tex> -- — функция переходов(англ. ''transition function'').

Для удобства можно ввести следующие обозначения== Процесс допуска ==Изначально автомат находится в стартовом состоянии <tex>s</tex>. Автомат считывает символы по очереди. При считывании очередного символа <tex>p_i</tex> автомат переходит в состояние <tex>\delta(q, p_i)</tex>, где <tex>q</tex> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.{{Определение|id=допускает|definition=Будем говорить, что автомат '''допускает''' (англ. ''accept'') слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.}}'''Замечание.''' Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную '''''«дьявольскую вершину»''''' (также '''''тупиковое состояние''''', '''''сток'''''), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину». == Способы представления =====Диаграмма переходов=== Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.:<tex>\bigcirc</tex> — нетерминальное состояние,:<tex>\circledcirc</tex> — терминальное состояние,:Стрелка <tex>\downarrow</tex> указывает на начальное состояние.{| class = "wikitable" !Пример!!Описание|-align="center"| style="background-color:white;" | [[Файл:Automata_Search.png|340px]]|Автомат для поиска образца в тексте для строки <tex>abbab</tex>.|-align="center"| style="background-color:white;" | [[Файл:Finite state machine 1.png|250 px]]|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b</tex>,без «дьявольской вершины». |-align="center"| style="background-color:white;" | [[Файл:Finite state machine 2.png|200 px]]|Автомат, принимающий непустые строки из чередующихся символов <tex>a</tex> и <tex>b</tex>, с «дьявольской вершиной». |-align="center"|} ===Таблица переходов=== Таблица переходов <tex>T (|Q| \times |\Sigma|)</tex>, дающая табличное представление функции <tex>\delta</tex>. <tex>M = (Q, \Sigma , \delta, q_0, F)</tex>, где*<tex>Q = {S_1, S_2}</tex>,*<tex>\Sigma = \{0, 1 \}</tex>,*<tex>q_0 = S_1</tex>,* <tex>F = {S_1}</tex>, *<tex>\delta</tex> {{---}} функция переходов, представленная таблицей::{| class="wikitable" border="1" style="border-collapse:collapse"! !! <center><tex>0</tex></center> !! <center><tex>1</tex></center>|-!<tex>S_1</tex> | <tex>S_2</tex> | <tex>S_1</tex>|-!<tex>S_2</tex> | <tex>S_1</tex> | <tex>S_2</tex>|} == Автоматные языки =={{Определение|definition='''Мгновенное описание''' ('''конфигурация''') (англ. ''snapshot'') {{---}} пара <tex>\langle q, \alpha \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</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>\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>.

<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>.

Множество <tex>L(\mathcal{A})=\{\alpha| \mid \exists t \in T : \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> --- язык называется '''языком автомата ''' (англ. ''automata's language'') <tex>\mathcal{A}</tex>.}}Иначе говоря, языком автомата является множество всех допускаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку. {{Определение|definition=Множество языков всех ДКА образует множество '''автоматных языков''' <tex>\mathrm{AUT}</tex>.