Недетерминированный конечный автомат

Сложность

Легкий 25%

Контенус

Недетерминированный конечный автомат

Мы привыкли рисовать автомат недетерминированный конечный, изображая состояния кружками, указывая начальное состояние входящей стрелкой, допускающие состояния двойным кружком или исходящей стрелкой, а переход из состояния q в состояние q' чтением буквы α посредством стрелка, идущая от q к q' и отмеченная α.

Недетерминированный конечный автомат A — это тройка (Vt, Q, T), где

Vt — словарь автомата;
Q — конечное множество состояний автомата;
T: Q × Vt → Q — частичное отображение, называемое переходной функцией автомата.

Заметим, что детерминированный автомат — это частный случай недетерминированного автомата, который сопоставляет любому элементу Q × Vt часть Q, содержащую ноль или один элемент (ровно один, если это полный автомат). Мы можем сказать о детерминированном автомате, что он неполный, если он может блокироваться, то есть если существуют состояние q и буква а, такие что T(q, a) = ∅. Если он полный, мы имеем следующее свойство:

Пусть A = (Vt, Q, T) — полный недетерминированный конечный автомат. Тогда для любого слова u ∈ V^*_ты и для каждого состояния q ∈ Q существует (не всегда единственное) состояние q' ∈ Q такое, что q(u)→Aq'.

Однако у недетерминизма есть существенное следствие: может быть несколько выводов, происходящих из начального состояния i, которые читают данное слово w, из которых некоторые могут быть заблокированы, а другие нет, и в этом последнем случае некоторые могут закончиться состоянием, принимающим и другие нет. Принятие происходит, если есть хотя бы одно успешное вычисление. Если все вычисления не удались, не будет другого способа узнать, кроме как изучить их все, прежде чем узнать, что слово w не распознано. Таким образом, правильным понятием является не понятие вычисления, а дерево вычислений, связанное со словом, прочитанным автоматом:

Для недетерминированного конечного автомата A дерево вывода с корнем q ∈ Q, порожденное чтением слова u, представляет собой дерево дважды помеченный, определяемый индукцией по u:
Если u = ε, то дерево сводится к своему корню q;
Если u = av, то у корня q есть исходящие переходы, помеченные a ∈ Vt, к различным деревьям вычислений, порожденным чтением v и чьи корни помечены состояниями T(q, a).

Дерево вывода строится так же, как и в случае детерминированного автомата. В случае недетерминированного конечного автомата он не является линейным и может представлять различные ветви, которые будут давать различные выводы, ведущие или не приводящие к распознаванию слова.

Слово u распознается недетерминированным автоматом A тогда и только тогда, когда один из листьев его дерева вычислений помечен допускающим состоянием.

Недетерминизм и распознаваемые слова

Рассмотрим следующий недетерминированный конечный автомат A = ({a, b}, {1, 2, 3}, ∆, {1}, {1}):

Принимается ли слово баабаб автоматом А?

Ни один лист не соответствует конечному состоянию, обратите внимание, что все листы попадают в колодец.

Подобно детерминированному автомату, можно построить слова, распознаваемые автоматом, просматривая входные строки и выходные столбцы. Затем слова длины n строятся путем возведения матрицы перехода в степень n.