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

Тип конечного автомата в теории автоматов

NFA для (0|1) ^* 1  (0|1) 3.
DFA для этого языка имеет не менее 16 состояний.

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

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

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

Используя алгоритм построения подмножества , каждый НКА можно перевести в эквивалентный ДКА; т. е. ДКА, распознающий тот же формальный язык . ^[1] Как и ДКА, НКА распознают только регулярные языки .

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

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

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

Существует по крайней мере два способа описания поведения NFA, и оба они эквивалентны. Первый способ использует недетерминизм в названии NFA. Для каждого входного символа NFA переходит в новое состояние до тех пор, пока все входные символы не будут потреблены. На каждом шаге автомат недетерминированно «выбирает» один из применимых переходов. Если существует по крайней мере один «счастливый запуск», т. е. некоторая последовательность выборов, приводящая к принимающему состоянию после полного потребления ввода, он принимается. В противном случае, т. е. если никакая последовательность выборов вообще не может потребить весь ввод ^[3] и привести к принимающему состоянию, ввод отклоняется. ^{[4] : 19  [5] : 319}

Во втором случае NFA потребляет строку входных символов, один за другим. На каждом шаге, когда применимы два или более переходов, он «клонирует» себя в соответствующее количество копий, каждая из которых следует за другим переходом. Если ни один переход не применим, текущая копия находится в тупике и «умирает». Если после потребления полного ввода любая из копий находится в состоянии принятия, ввод принимается, в противном случае он отклоняется. ^{[4] : 19–20  [6] : 48  [7] : 56}

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

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

Автомат

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

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

Здесь обозначает множество степеней . ${\displaystyle {\mathcal {P}}(Q)}$ ${\displaystyle Q}$

Распознаваемый язык

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

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

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

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

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

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

Начальное состояние

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

Пример

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

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

Все возможные последовательности состояний для входной строки "1011" показаны на нижнем рисунке. Строка принимается, поскольку одна последовательность состояний удовлетворяет вышеприведенному определению; неважно, что другие последовательности не удовлетворяют этому определению. Рисунок можно интерпретировать несколькими способами: ${\displaystyle M}$

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

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

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

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

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

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

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

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

NFA с ε-ходами

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

то есть, если чтение может перевести автомат из его начального состояния в некоторое принимающее состояние в ^{[4] : ​​25} ${\displaystyle w}$ ${\displaystyle q_{0}}$ ${\displaystyle F.}$

Пример

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

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

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

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

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

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

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

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

и

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

Необходимо различать функции перехода и , а именно и и их расширения до строк и соответственно. По построению не имеет ε-переходов. ${\displaystyle M}$ ${\displaystyle M',}$ ${\displaystyle \delta }$ ${\displaystyle \delta ',}$ ${\displaystyle \delta }$ ${\displaystyle \delta '^{*},}$ ${\displaystyle M'}$

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

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

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

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

• Если содержит состояние в , то содержит то же самое состояние, которое лежит в . ${\displaystyle \delta '^{*}(q_{0},w)}$ ${\displaystyle F'\setminus \{q_{0}\},}$ ${\displaystyle \delta ^{*}(q_{0},w)}$ ${\displaystyle F}$
• Если содержит и , то также содержит состояние, а именно: ${\displaystyle \delta '^{*}(q_{0},w)}$ ${\displaystyle q_{0},}$ ${\displaystyle q_{0}\in F,}$ ${\displaystyle \delta ^{*}(q_{0},w)}$ ${\displaystyle F,}$ ${\displaystyle q_{0}.}$
• Если содержит и , но тогда существует состояние в , и то же самое состояние должно быть в ^{[4] : 26–27} ${\displaystyle \delta '^{*}(q_{0},w)}$ ${\displaystyle q_{0},}$ ${\displaystyle q_{0}\not \in F,}$ ${\displaystyle q_{0}\in F',}$ ${\displaystyle E(q_{0})\cap F}$ ${\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a)).}$

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

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

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

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

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

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

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

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

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

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

Выполнение

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

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

Сложность

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

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

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

Смотрите также

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

Примечания

1. Мартин, Джон (2010). Введение в языки и теорию вычислений . McGraw Hill. стр. 108. ISBN 978-0071289429.
2. Рабин, МО; Скотт, Д. (апрель 1959 г.). «Конечные автоматы и проблемы их принятия решений». IBM Journal of Research and Development . 3 (2): 114–125. doi :10.1147/rd.32.0114.
3. Последовательность выбора может привести к «тупику», где для текущего входного символа не применим ни один переход; в этом случае она считается неудачной.
4. Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.
5. Альфред В. Ахо и Джон Э. Хопкрофт и Джеффри Д. Ульман (1974). Проектирование и анализ компьютерных алгоритмов . Reading/MA: Addison-Wesley. ISBN 0-201-00029-6.
6. Майкл Сипсер (1997). Введение в теорию вычислений. Бостон/Массачусетс: PWS Publishing Co. ISBN 0-534-94728-X.
7. Джон Э. Хопкрофт и Раджив Мотвани и Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления (PDF) . Upper Saddle River/NJ: Addison Wesley. ISBN 0-201-44124-1.
8. FOLDOC Бесплатный онлайн-словарь по вычислительной технике, Конечный автомат
9. Крис Калабро (27 февраля 2005 г.). «Разрушение NFA и DFA» (PDF) . cseweb.ucsd.edu . Проверено 6 марта 2023 г.
10. Allan, C., Avgustinov, P., Christensen, AS, Hendren, L., Kuzins, S., Lhoták, O., de Moor, O., Sereni, D., Sittampalam, G. и Tibble, J. 2005. Добавление сопоставления трассировки со свободными переменными в AspectJ Архивировано 18 сентября 2009 г. в Wayback Machine . В трудах 20-й ежегодной конференции ACM SIGPLAN по объектно-ориентированному программированию, системам, языкам и приложениям (Сан-Диего, Калифорния, США, 16–20 октября 2005 г.). OOPSLA '05. ACM, Нью-Йорк, штат Нью-Йорк, 345-364.
11. Исторически показано в: Meyer, AR; Stockmeyer, LJ (1972-10-25). "Проблема эквивалентности для регулярных выражений с возведением в квадрат требует экспоненциального пространства". Труды 13-го ежегодного симпозиума по теории коммутации и автоматов (SWAT) . США: IEEE Computer Society: 125–129. doi :10.1109/SWAT.1972.29.Для современного представления см. [1]
12. Альварес, Карме; Дженнер, Биргит (1993-01-04). "Очень сложный класс подсчета логарифмического пространства". Теоретическая информатика . 107 (1): 3–30. doi :10.1016/0304-3975(93)90252-O. ISSN  0304-3975.

Ссылки

• М. О. Рабин и Д. Скотт, «Конечные автоматы и проблемы их принятия решений», 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, Reading Massachusetts, 1979. ISBN 0-201-02988-X . (См. главу 2.)