Изменения

{{В разработкеОпределение|definition='''Детерминированный конечный автомат (ДКА)''' (англ. ''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> — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.

Детерминированный конечный Будем говорить, что автомат'''допускает''' (ДКАангл. ''accept'') --- набор из пяти элементов <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>\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>.