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

НКА для (0|1) ^*  1 (0|1) ³ .
DFA для этого языка имеет как минимум 16 состояний.

В теории автоматов называется конечный автомат детерминированным конечным автоматом (ДКА), если

• каждый из его переходов однозначно определяется его исходным состоянием и входным символом, и
• чтение входного символа требуется для каждого перехода состояний.

Недетерминированный конечный автомат ( NFA ) или недетерминированный конечный автомат не обязан подчиняться этим ограничениям. В частности, каждый DFA также является NFA. Иногда термин NFA используется в более узком смысле, имея в виду NFA, который не является DFA, но не в этой статье.

Используя алгоритм построения подмножества , каждый NFA можно преобразовать в эквивалентный DFA; т. е. DFA, распознающий тот же формальный язык . Как и DFA, NFA распознают только обычные языки .

НФА были представлены в 1959 году Майклом О. Рабином и Даной Скотт . которые также показали свою эквивалентность DFA. NFA используются при реализации регулярных выражений : конструкция Томпсона представляет собой алгоритм компиляции регулярного выражения в NFA, который может эффективно выполнять сопоставление с образцом в строках. И наоборот, алгоритм Клини можно использовать для преобразования NFA в регулярное выражение (размер которого обычно экспоненциален во входном автомате).

NFA были обобщены несколькими способами, например, недетерминированные конечные автоматы с ε-ходами , преобразователи с конечным состоянием , автоматы с выталкиванием , альтернативные автоматы , ω-автоматы и вероятностные автоматы . Помимо DFA, существуют и другие известные частные случаи NFA. являются однозначными конечными автоматами (UFA) и самопроверяющиеся конечные автоматы (SVFA).

Неофициальное знакомство

Есть два способа описать поведение NFA, и оба они эквивалентны. Первый способ использует недетерминизм в названии NFA. Для каждого входного символа NFA переходит в новое состояние до тех пор, пока все входные символы не будут использованы. На каждом шаге автомат недетерминированно «выбирает» один из подходящих переходов. Если существует хотя бы один «счастливый ход», то есть некоторая последовательность выборов, ведущая к состоянию принятия после полного использования входных данных, он принимается. В противном случае, т.е. если никакая последовательность выбора вообще не может использовать весь входной сигнал и приводят к состоянию принятия, ввод отклоняется.

Во втором случае NFA принимает строку входных символов один за другим. На каждом этапе, когда применимы два или более перехода, он «клонирует» себя в соответствующее количество копий, каждая из которых следует за другим переходом. Если переход не применим, текущая копия находится в тупике и «умирает». Если после использования всех входных данных какая-либо из копий находится в состоянии принятия, входные данные принимаются, в противном случае они отклоняются.

Формальное определение

Более элементарное введение формального определения см. в теории автоматов .

Автомат

NFA кортежем формально представлен из 5 $(Q,\Sigma ,\delta ,q_{0},F)$, состоящий из

• конечное множество состояний $Q$,
• конечный набор входных символов $\Sigma$,
• функция перехода $\delta$ : $Q\times \Sigma \rightarrow {\mathcal {P}}(Q)$,
• начальное стартовое (или ) состояние $q_{0}\in Q$, и
• набор состояний $F$ различаются как принимающие (или конечные ) состояния $F\subseteq Q$.

Здесь, ${\mathcal {P}}(Q)$ обозначает мощности набор $Q$.

Признанный язык

Учитывая НФА $M=(Q,\Sigma ,\delta ,q_{0},F)$, его признанный язык обозначается $L(M)$и определяется как набор всех строк в алфавите $\Sigma$ которые принимаются $M$.

В соответствии с приведенными выше неформальными объяснениями существует несколько эквивалентных формальных определений строки. $w=a_{1}a_{2}...a_{n}$ быть принятым $M$:

• $w$ принимается, если последовательность состояний, $r_{0},r_{1},...,r_{n}$, существует в $Q$ такой, что:
  1. $r_{0}=q_{0}$
  2. $r_{i+1}\in \delta (r_{i},a_{i+1})$, для $i=0,\ldots ,n-1$
  3. $r_{n}\in F$.

На словах первое условие говорит о том, что машина запускается в стартовом состоянии. $q_{0}$. Второе условие гласит, что для каждого символа строки $w$, машина будет переходить из состояния в состояние в соответствии с функцией перехода. $\delta$. Последнее условие говорит о том, что машина принимает $w$ если последний ввод $w$ приводит к остановке машины в одном из принимающих состояний. Для того, чтобы $w$ быть принятым $M$, не требуется, чтобы каждая последовательность состояний заканчивалась состоянием принятия, достаточно, если это так. В противном случае, т.е. если вообще невозможно получить из $q_{0}$ в состояние из $F$ следуя $w$, говорят, что автомат отвергает строку. Набор струн $M$ принимает язык признанный , $M$ и этот язык обозначается $L(M)$.

• Альтернативно, $w$ принимается, если $\delta ^{*}(q_{0},w)\cap F\not =\emptyset$, где $\delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)$ определяется рекурсивно :
  1. $\delta ^{*}(r,\epsilon )=\{r\}$ где $\epsilon$ пустая строка, и
  2. $\delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)$ для всех $x\in \Sigma ^{*},a\in \Sigma$.

Другими словами, $\delta ^{*}(r,x)$ это набор всех состояний, достижимых из состояния $r$ потребляя строку $x$. Строка $w$ принимается, если какое-то принимающее состояние в $F$ может быть достигнуто из начального состояния $q_{0}$ потребляя $w$.

Исходное состояние

Приведенное выше определение автомата использует одно начальное состояние , в котором нет необходимости. Иногда NFA определяются набором начальных состояний. Существует простая конструкция, которая переводит НКА с несколькими начальными состояниями в НКА с одним начальным состоянием, что обеспечивает удобную систему обозначений.

Пример

Диаграмма состояний M ​ . Он не является детерминированным, поскольку в состоянии p чтение 1 может привести к p или к q .	Все возможные прогоны M во входной строке «10».
Все возможные значения M во входной строке «1011». Метка дуги: входной символ, метка узла : состояние, зеленый : начальное состояние, красный : принимающее состояние(я).

Следующий автомат $M$, с двоичным алфавитом, определяет, заканчивается ли вход на 1. Позволять $M=(\{p,q\},\{0,1\},\delta ,p,\{q\})$ где функция перехода $\delta$ может быть определен с помощью этой таблицы переходов состояний (см. верхний левый рисунок):

Вход Состояние	0	1
$p$	$\{p\}$	$\{p,q\}$
$q$	$\emptyset$	$\emptyset$

С момента набора $\delta (p,1)$ содержит более одного состояния, $M$ является недетерминированным. Язык $M$ может быть описан обычным языком, заданным регулярным выражением (0|1)*1.

Все возможные последовательности состояний для входной строки «1011» показаны на нижнем рисунке. Строка принимается $M$ поскольку одна последовательность состояний удовлетворяет приведенному выше определению; не имеет значения, что другие последовательности этого не делают. Картину можно интерпретировать двояко:

• С точки зрения приведенного выше объяснения «счастливого пути», каждый путь на картинке обозначает последовательность вариантов выбора. $M$.
• Что касается объяснения «клонирования», в каждом вертикальном столбце показаны все клоны $M$ в данный момент времени множественные стрелки, исходящие из узла, указывают на клонирование, узел без исходящих стрелок указывает на «смерть» клона.

Возможность прочтения одной и той же картинки двумя способами также указывает на эквивалентность обоих приведенных выше объяснений.

• Учитывая первое из приведенных выше формальных определений, «1011» принимается, так как при его чтении $M$ может пересекать последовательность состояний $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$, удовлетворяющий условиям 1–3.
• Что касается второго формального определения, вычисления снизу вверх показывают, что $\delta ^{*}(p,\epsilon )=\{p\}$, следовательно $\delta ^{*}(p,1)=\delta (p,1)=\{p,q\}$, следовательно $\delta ^{*}(p,10)=\delta (p,0)\cup \delta (q,0)=\{p\}\cup \{\}$, следовательно $\delta ^{*}(p,101)=\delta (p,1)=\{p,q\}$, и, следовательно, $\delta ^{*}(p,1011)=\delta (p,1)\cup \delta (q,1)=\{p,q\}\cup \{\}$; поскольку это множество не не пересекается с $\{q\}$, строка «1011» принимается.

Напротив, строка «10» отклоняется $M$ (все возможные последовательности состояний для этого входа показаны на верхнем правом рисунке), поскольку невозможно достичь единственного принимающего состояния, $q$, прочитав последний символ 0. Пока $q$ может быть достигнуто после потребления начальной «1», это не означает, что ввод «10» принят; скорее, это означает, что будет принята входная строка «1».

Эквивалентность DFA

Детерминированный конечный автомат (DFA) можно рассматривать как особый вид NFA, в котором для каждого состояния и символа функция перехода имеет ровно одно состояние. Таким образом, ясно, что любой формальный язык , который может быть распознан DFA, может быть распознан и NFA.

И наоборот, для каждого NFA существует DFA, распознающий один и тот же формальный язык. DFA может быть построен с использованием конструкции powerset .

Этот результат показывает, что NFA, несмотря на свою дополнительную гибкость, не способны распознавать языки, которые не могут быть распознаны некоторыми DFA. На практике это также важно для преобразования более простых в построении NFA в более эффективно исполняемые DFA. Однако, если NFA имеет n состояний, результирующий DFA может иметь до 2 состояний. ^н штатов, что иногда делает строительство нецелесообразным для крупных НФА.

NFA с ε-ходами

Недетерминированный конечный автомат с ε-ходами (NFA-ε) является дальнейшим обобщением NFA. В автомате такого типа функция перехода дополнительно определяется на пустой строке ε. Переход без использования входного символа называется ε-переходом и обозначается на диаграммах состояний стрелкой с надписью «ε». ε-переходы обеспечивают удобный способ моделирования систем, текущие состояния которых точно не известны: т. е., если мы моделируем систему и неясно, должно ли текущее состояние (после обработки некоторой входной строки) быть q или q', тогда мы можем добавить ε-переход между этими двумя состояниями, тем самым переводя автомат в оба состояния одновременно.

Формальное определение

NFA -ε формально представляется кортежем из пяти чисел : $(Q,\Sigma ,\delta ,q_{0},F)$, состоящий из

• конечное множество состояний ​ $Q$
• конечный набор входных символов, называемый алфавитом $\Sigma$
• перехода функция $\delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow {\mathcal {P}}(Q)$
• начальное стартовое (или ) состояние $q_{0}\in Q$
• набор состояний $F$ различаются как принимающие (или конечные ) состояния $F\subseteq Q$.

Здесь, ${\mathcal {P}}(Q)$ обозначает мощности набор $Q$ и $\epsilon$ обозначает пустую строку.

ε-замыкание состояния или набора состояний

Для государства $q\in Q$, позволять $E(q)$ обозначают множество состояний, достижимых из $q$ следуя ε-переходам в переходной функции $\delta$, то есть, $p\in E(q)$ если существует последовательность состояний $q_{1},...,q_{k}$ такой, что

• $q_{1}=q$,
• $q_{i+1}\in \delta (q_{i},\varepsilon )$ для каждого $1\leq i<k$, и
• $q_{k}=p$.

$E(q)$ известно как эпсилон-замыкание (также ε-замыкание ) $q$.

ε-замыкание множества $P$ состояний NFA определяется как набор состояний, достижимых из любого состояния в $P$ после ε-переходов. Формально для $P\subseteq Q$, определять $E(P)=\bigcup \limits _{q\in P}E(q)$.

Расширенная функция перехода

Подобно NFA без ε-ходов, функция перехода $\delta$ NFA-ε можно расширить до строк. Неофициально, $\delta ^{*}(q,w)$ обозначает набор всех состояний, которых мог достичь автомат при запуске в состоянии $q\in Q$ и читаем строку $w\in \Sigma ^{*}.$ Функция $\delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)$ можно определить рекурсивно следующим образом.

• $\delta ^{*}(q,\varepsilon )=E(q)$, для каждого штата $q\in Q,$ и где $E$ обозначает эпсилон-замыкание;

Неформально: чтение пустой строки может вывести автомат из состояния. $q$ к любому состоянию эпсилон-замыкания $q.$

• ${\textstyle \delta ^{*}(q,wa)=\bigcup _{r\in \delta ^{*}(q,w)}E(\delta (r,a)),}$ для каждого штата $q\in Q,$ каждая строка $w\in \Sigma ^{*}$ и каждый символ $a\in \Sigma .$

Неофициально: чтение строки $w$ может вывести автомат из состояния $q$ в любое государство $r$ в рекурсивно вычисленном наборе $\delta ^{*}(q,w)$; после этого, читая символ $a$ может отогнать его от $r$ в любое состояние в эпсилон-замыкании $\delta (r,a).$

Говорят, что автомат принимает строку $w$ если

$\delta ^{*}(q_{0},w)\cap F\neq \emptyset ,$

то есть если читать $w$ может вывести автомат из стартового состояния $q_{0}$ в какое-то принимающее государство в $F.$

Пример

Диаграмма состояний M ​

Позволять $M$ быть NFA-ε с двоичным алфавитом, который определяет, содержит ли вход четное количество нулей или четное количество единиц. Обратите внимание, что 0 вхождений также является четным числом вхождений.

В формальных обозначениях пусть $$M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\delta ,S_{0},\{S_{1},S_{3}\})$$ где отношение перехода $\delta$ может быть определен этой таблицей перехода состояний :

Вход Состояние	0	1	е
С 0	{}	{}	{ С 1 , С 3 }
С 1	{ С 2 }	{ С 1 }	{}
SS2	{ С 1 }	{ С 2 }	{}
С 3	{ С 3 }	{ С 4 }	{}
С 4	{ С 4 }	{ С 3 }	{}

$M$ можно рассматривать как объединение двух DFA : одного с государствами $\{S_{1},S_{2}\}$ а другой с состояниями $\{S_{3},S_{4}\}$. Язык $M$ может быть описан обычным языком, заданным этим регулярным выражением $(1^{*}01^{*}0)^{*}\cup (0^{*}10^{*}1)^{*}$. Мы определяем $M$ используя ε-ходы, но $M$ можно определить без использования ε-ходов.

Эквивалент NFA

Чтобы показать, что NFA-ε эквивалентен NFA, сначала заметим, что NFA является частным случаем NFA-ε, поэтому осталось показать, что для каждого NFA-ε существует эквивалентный NFA.

Учитывая NFA с эпсилон-ходами $M=(Q,\Sigma ,\delta ,q_{0},F),$ определить NFA $M'=(Q,\Sigma ,\delta ',q_{0},F'),$ где

$F'={\begin{cases}F\cup \{q_{0}\}&{\text{ if }}E(q_{0})\cap F\neq \{\}\\F&{\text{ otherwise }}\\\end{cases}}$

и

$\delta '(q,a)=\delta ^{*}(q,a)$ для каждого штата $q\in Q$ и каждый символ $a\in \Sigma ,$ используя расширенную функцию перехода $\delta ^{*}$ определено выше.

Следует различать переходные функции $M$ и $M',$ а именно $\delta$ и $\delta ',$ и их расширения до строк, $\delta$ и $\delta '^{*},$ соответственно. По конструкции, $M'$ не имеет электронных переходов.

Можно доказать, что $\delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)$ для каждой строки $w\neq \varepsilon$, индукцией по длине $w.$

На основании этого можно показать, что $\delta '^{*}(q_{0},w)\cap F'\neq \{\}$ тогда и только тогда, когда $\delta ^{*}(q_{0},w)\cap F\neq \{\},$ для каждой строки $w\in \Sigma ^{*}:$

• Если $w=\varepsilon ,$ это следует из определения $F'.$
• В противном случае, пусть $w=va$ с $v\in \Sigma ^{*}$ и $a\in \Sigma .$

От $\delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)$ и $F\subseteq F',$ у нас есть $$\delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};$$ нам еще предстоит показать " $\Rightarrow$" направление.

• Если $\delta '^{*}(q_{0},w)$ содержит состояние в $F'\setminus \{q_{0}\},$ затем $\delta ^{*}(q_{0},w)$ содержит одно и то же состояние, которое лежит в $F$.
• Если $\delta '^{*}(q_{0},w)$ содержит $q_{0},$ и $q_{0}\in F,$ затем $\delta ^{*}(q_{0},w)$ также содержит состояние в $F,$ а именно $q_{0}.$
• Если $\delta '^{*}(q_{0},w)$ содержит $q_{0},$ и $q_{0}\not \in F,$ но $q_{0}\in F',$ тогда существует состояние в $E(q_{0})\cap F$, и это же состояние должно находиться в ${\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a)).}$

Поскольку NFA эквивалентен DFA, NFA-ε также эквивалентен DFA.

Свойства замыкания

Составленный NFA, признающий объединение языков некоторых данных NFA. Н ( с ) и Н ( т ) . Для входной строки w в языковом объединении составной автомат следует ε-переходу из q в начальное состояние (левый цветной кружок) соответствующего подавтомата — Н ( с ) или N ( t ) — который, следуя w , может достичь состояния принятия (правый цветной кружок); оттуда состояние f может быть достигнуто другим ε-переходом. Из-за ε-переходов составленный NFA является правильно недетерминированным, даже если оба Н ( с ) и N ( t ) – ДФА; и наоборот, построение ДКА для языка объединения (даже двух ДКА) гораздо сложнее.

Набор языков, распознаваемых НФА, замыкается при следующих операциях. Эти операции замыкания используются в алгоритме построения Томпсона , который конструирует NFA из любого регулярного выражения . Их также можно использовать для доказательства того, что NFA распознают именно обычные языки .

• Союз (ср. картинку); то есть, если язык L ₁ принимается некоторым НКА А ₁ и L ₂ некоторым А ₂ , то можно построить НКА А _u , который принимает язык L ₁ ∪ L ₂ .
• Пересечение; аналогично, из A ₁ и A ₂ НКА A _i, можно построить допускающую L ₁ ∩ L ₂ .
• Конкатенация
• Отрицание; аналогично, из A ₁ НКА An _{, который принимает Σ} можно построить ^* \ Л ₁ .
• Закрытие Клини

Поскольку НКА эквивалентны недетерминированному конечному автомату с ε-ходами (НКА-ε), указанные выше замыкания доказываются с использованием свойств замыкания НКА-ε.

Характеристики

Машина запускается в указанном начальном состоянии и считывает строку символов из своего алфавита . Автомат использует функцию перехода состояний Δ для определения следующего состояния, используя текущее состояние и только что прочитанный символ или пустую строку. Однако «следующее состояние NFA зависит не только от текущего события ввода, но и от произвольного количества последующих событий ввода. Пока эти последующие события не произойдут, невозможно определить, в каком состоянии находится машина». Если, когда автомат завершил чтение, он находится в состоянии принятия, говорят, что NFA принимает строку, в противном случае говорят, что он отклоняет строку.

Набор всех строк, принимаемых NFA, — это язык, который принимает NFA. Этот язык является обычным языком .

Для каждого NFA детерминированный конечный автомат можно найти (DFA), который принимает тот же язык. Следовательно, можно преобразовать существующий NFA в DFA с целью реализации (возможно) более простой машины. Это можно выполнить с помощью конструкции powerset , которая может привести к экспоненциальному росту количества необходимых состояний. Формальное доказательство конструкции Powerset можно найти в статье о конструкции Powerset .

Выполнение

Существует множество способов реализации NFA:

• Преобразование в эквивалентный DFA. В некоторых случаях это может привести к экспоненциальному увеличению числа состояний.
• Сохраняйте заданную структуру данных всех состояний, в которых в данный момент может находиться NFA. При потреблении входного символа объединяйте результаты функции перехода, примененной ко всем текущим состояниям, чтобы получить набор следующих состояний; если ε-ходы разрешены, включить все состояния, достижимые таким ходом (ε-замыкание). Каждый шаг требует не более s ² вычислений, где s — количество состояний НКА. При потреблении последнего входного символа, если одно из текущих состояний является конечным, машина принимает строку. Строка длины n может быть обработана за время O ( ns ² ), и пространство O ( s ).
• Создайте несколько копий. Для каждого n- путевого решения NFA создает до n -1 копий машины. Каждый войдет в отдельное состояние. Если после использования последнего входного символа хотя бы одна копия NFA находится в состоянии принятия, NFA примет. (Это также требует линейного хранения по отношению к количеству состояний NFA, поскольку для каждого состояния NFA может быть одна машина.)
• Явно распространяйте токены через структуру перехода NFA и сопоставляйте их всякий раз, когда токен достигает конечного состояния. Иногда это полезно, когда NFA должен закодировать дополнительный контекст событий, вызвавших переход. (Для реализации, использующей этот метод для отслеживания ссылок на объекты, посмотрите Tracematches.)

Сложность

• Можно за линейное время решить проблему пустоты для NFA, т. е. проверить, пуст ли язык данного NFA. Для этого мы можем просто выполнить поиск в глубину из начального состояния и проверить, можно ли достичь какого-то конечного состояния.
• PSPACE - полная проверка данного NFA, является ли он универсальным , т. е. существует ли строка, которую он не принимает. Как следствие, то же самое верно и для проблемы включения , т. е. для двух NFA язык одного является подмножеством языка другого.
• Учитывая, что на входе NFA A и целое число n, проблема подсчета определения того, сколько слов длины n принимается A , является неразрешимой; это #P -сложно . Фактически, эта проблема является полной (при экономных редукциях ) для класса сложности SpanL .

Применение НФА

NFA и DFA эквивалентны в том смысле, что если язык распознается NFA, он также распознается DFA и наоборот. Установление такой эквивалентности важно и полезно. Это полезно, потому что построить NFA для распознавания данного языка иногда намного проще, чем построить DFA для этого языка. Это важно, поскольку NFA можно использовать для уменьшения сложности математической работы, необходимой для установления многих важных свойств в теории вычислений . Например, гораздо проще доказать свойства замыкания регулярных языков, используя NFA, чем DFA.

См. также

• Детерминированный конечный автомат
• Двусторонний недетерминированный конечный автомат
• Нажимной автомат
• Недетерминированная машина Тьюринга

Ссылки

• М. О. Рабин и Д. Скотт, «Конечные автоматы и проблемы их принятия решений», IBM Journal of Research and Development , 3 :2 (1959), стр. 115–125.
• Майкл Сипсер, Введение в теорию вычислений . PWS, Бостон. 1997. ISBN   0-534-94728-X . (см. раздел 1.2: Недетерминизм, стр. 47–63.)
• Джон Э. Хопкрофт и Джеффри Д. Уллман, Введение в теорию автоматов, языки и вычисления , издательство Addison-Wesley Publishing, Ридинг, Массачусетс, 1979. ISBN   0-201-02988-X . (См. главу 2.)