Детерминированный конечный автомат
Детерминированный конечный автомат — это конечный автомат, в котором для каждой пары «текущее состояние и входной символ» существует ровно один следующий переход. Поэтому, зная начальное состояние и слово на входе, можно однозначно определить весь путь автомата и его результат.
Точное условие детерминированности
Обозначим множество состояний через \(Q\), входной алфавит — через \(\Sigma\), а функцию переходов — через \(\delta\). Для каждой пары \((q,a)\), где \(q\in Q\) и \(a\in\Sigma\), должен быть определён один и только один результат. Это означает, что автомат не может одновременно перейти из одного состояния по одному символу в разные состояния и не может не иметь перехода для такой пары.
После чтения каждого символа автомат находится ровно в одном состоянии. Если слово обрабатывается последовательно, очередное состояние вычисляется по правилу перехода между состояниями. Начальное состояние выбирается до чтения слова, а в конце проверяется, является ли полученное состояние заключительным.
Пусть есть состояния \(q_0\) и \(q_1\), а алфавит состоит из символов \(0\) и \(1\). Из \(q_0\) по \(0\) автомат переходит в \(q_1\), по \(1\) — остаётся в \(q_0\). Из \(q_1\) по \(0\) переходит в \(q_0\), по \(1\) — остаётся в \(q_1\). Для каждой из четырёх пар состояния и символа задан ровно один переход, поэтому автомат детерминирован. Если начальное состояние — \(q_0\), слово \(01\) переводит автомат сначала в \(q_1\), затем остаётся в \(q_1\).
Детерминированность означает однозначность перехода, а не обязательное принятие любого слова. ДКА может отклонить слово, если после его обработки окажется состояние, не входящее в множество заключительных. В недетерминированном автомате для одной пары «состояние и символ» могут существовать несколько вариантов перехода или ни одного.
В автомате из состояния \(q_2\) по символу \(a\) есть переходы сразу в \(q_0\) и \(q_1\). Может ли такой автомат быть детерминированным?
Главное
- ДКА имеет ровно один следующий переход для каждой пары «состояние — входной символ».
- Его поведение на любом слове однозначно определяется начальным состоянием и функцией переходов.
- Детерминированность переходов не означает, что автомат принимает все слова.