*Детерминированный конечный автомат* (ДКА, deterministic finite automaton, DFA) – это модель вычисления, заданная кортежем `A = (Sigma, Q, q_0, delta, F)`, где:
1. `Sigma` – алфавит, то есть конечное множество входных символов;
2. `Q` – конечное множество состояний;
3. `q_0 in Q` – начальное состояние;
4. `delta: Q xx Sigma -> Q` – функция перехода, то есть «программа», которая исполняет детерминированный конечный автомат. `delta` вычисляет следующее состояние `p = delta(q, a)`, где `p, q in Q, a in Sigma`;
5. `F sube Q` – множество финальных состояний (для автомата-распознавателя)
Для автомата-преобразователя вместо `F` нужно задать функцию выхода `lambda: Q -> Phi` (автомат Мура) или `lambda: Q xx Sigma -> Phi` (автомат Мили), где `Phi` - множество выходных символов.
--
Для того чтобы увидеть, что ДКА, заданный `А`, принимает строку `w`, мы «выполняем» `А` на
`w = a_1 a_2 ... a_n` следующим образом: `delta(q_0, a_1) = q_1`, `delta(q_1, a_2) = q_2` ...
`delta(q_{n-1}, a_n) = q_n`. `A` принимает `w` тогда и только тогда, когда `q_n in F`,
то есть если `q_n` является одним из финальных (принимающих) состояний. В противном случае мы говорим, что ДКА отклоняет `w`.
--
Предположим, что мы хотим спроектировать детерминированный конечный
автомат для языка L01, в котором допустимы только цепочки символов, содержащие 01.
Пусть `Sigma = {0, 1}`, `Q = {q_0, q_1, q_2}` и `F = {q_1}`. Существует два способа
представить `delta`: в форме диаграммы переходов либо в форме таблицы переходов.
Недетерминированный конечный автомат (НКА, nondeterministic finite automaton, NFA)
определяется аналогично ДКА, за исключением того, что переходная функция `delta` становится переходным отношением, то есть
`delta in Q xx Sigma xx Q`, то есть на одной и той же паре `(q, a)` может существовать более
одного возможного нового состояния (или ни одного).
Также мы можем смотреть на `delta` как на `delta : Q xx Sigma -> P(Q)`, где `P(Q)` – это множество подмножеств `Q`.
НДКА для языка Ln - `n`-ый символ с конца равен 1.
Теорема *Детерминированный и недетерминированный конечные автоматы являются эквивалентными.*
Очевидно, что ДКА – это особый случай НКА.
Таким образом, остается доказать, что каждый НКА может быть перепроектирован как ДКА, что осуществляется через построение подмножеств.
Сначала мы принимаем допущение, что НКА `N` не имеет `varepsilon`-переходов. Пусть `M` это ДКА, и тогда `Q_M = P(Q_N)`,
где `P(Q_N)` – состоит из всех возможных подмножеств множеств `Q_N`, и `delta_M(Q, a) := bigcup_{q in Q} delta_N(q, a)`,
где `Q in P(Q_N)`.
Также `F_M = {Q in P(Q_N) : Q cap F_N != emptyset}` и `(q_M)_0 := {(q_N)_0}`.
Если `N` имеет `varepsilon`-переходы, то `delta_M(Q, a) := bigcup_{q in Q} varepsilon-closure(delta_N(q, a))`.
--
Отметим, что происходит экспоненциальный рост состояний, поскольку `|P(Q_N)| = 2^{|QN|}`.
Мы симулируем более выразительную модель вычисления (НКА) с помощью более ограниченной (ДКА).
--
Рассмотрим пример преобразования из НКА для L2 (L2 – это множество строк, где предпоследний символ равен 0) в ДКА.
Описанный КА использует только одну ячейку памяти, в которой хранится текущее состояние
и может только распознавать или преобразовывать цепочки символов.
Если добавить в КА возможность использовать память и выполнять действия, то можно описать любое вычислительное устройство (компьютер).
В функцию перехода добавляются параметры, связанные с текущим состоянием памяти, а результат
включает не только изменение состояния, но и изменение памяти. Для диаграмм, описывающих КА общего вида, используется, например, UML.

--
Различают конечные автоматы
* с конечной памятью (можно свести к КА без памяти, включив состояние памяти в номер состояния,
что существенно усложняет определение КА);
* с бесконечной памятью (рассматривают обычно КА с памятью организованной в форме стека, такие КА используются в компиляторах).
Объекты в ООП рассматриваются как КА с памятью.
---
##### Задания для практики
1. Формат числа описывается следующей схемой

Определите ДКА для ввода числа
2. Определите ДКА, проверяющий что строка из букв a,b,c содержит буквы a и b.
3. Определите ДКА, проверяющий что строка из букв a,b,c имеет длину 3 и является перестановкой букв a,b,c.
--
[Редактор и исполнитель конечных автоматов](http://fsm-simulator.info/App/Designer)