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

НКА для ${\displaystyle (0|1)^{*}1;(0|1)^{3}}$.
Для этого языка у ДКА будет по меньшей мере 16 состояний

Недетерминированный конечный автомат (НКА, англ. nondeterministic finite automaton, NFA) — это детерминированный конечный автомат (ДКА, англ. deterministic finite automaton, DFA), который не выполняет следующие условия:

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

В частности, любой ДКА является также НКА.

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

НКА предложили в 1959 году Михаэль О. Рабин и Дана Скотт^[2], которые показали его эквивалентность ДКА. НКА используется в реализации регулярных выражений — построение Томпсона^[англ.] является алгоритмом для преобразования регулярного выражения в НКА, который может эффективно распознавать шаблон строк. Обратно, алгоритм Клини^[англ.] можно использовать для преобразования НКА в регулярное выражение, размер которого в общем случае экспоненциально зависит от размера автомата.

НКА обобщён многими путями, например: недетерминированным конечным автоматом с ε-переходами, преобразователями с конечным числом состояний, автоматами с магазинной памятью, альтернирующими автоматами, ω-автоматами и вероятностными автоматами. Кроме ДКА известны другие специальные случаи НКА — однозначные конечные автоматы^[англ.] (англ. unambiguous finite automata, UFA) и самопроверочные конечные автоматы^[англ.] (англ. self-verifying finite automata, SVFA).

Неформальное введение

Есть несколько неформальных эквивалентных описаний:

• НКА, подобно ДКА, принимает строку входных символов. Для каждого входного символа он переходит в новое состояние, пока не обработает все входные символы. На каждом шаге автомат произвольным образом выбирает один из возможных переходов. Если существует «удачный проход», то есть некоторая последовательность выборов, приводящая к конечному состоянию после полной выборки входной строки, то строка принимается. Если же нет последовательности, которая после обработки всей входной строки^[3] приводит автомат в конечное состояние, то входная строка отвергается^[4][5].
• Пусть опять НКА принимает строку входных символов, один символ за другим. На каждом шаге, где два или более перехода оказываются допустимыми, автомат «клонирует» себя на нужное число копий, каждая из которых осуществляет различные переходы. Если никакой из переходов не может быть осуществлён, текущая копия является тупиком и «умирает». Если после выборки всех символов из входной строки какая-либо из копий переходит в конечное состояние, входная строка принимается, в противном случае — отвергается^[6][7][8].

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

Для более элементарного введения в формальное определение см. статью «Теория автоматов».

Автоматы

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

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

Здесь ${\displaystyle 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}$.

Словами. Первое условие гласит, что машина начинает работу из состояния ${\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)}$^[9][10].

• Альтернативно, ${\displaystyle w}$ принимается, если ${\displaystyle \Delta ^{*}(q_{0},w)\cap F\not =\emptyset }$, где ${\displaystyle \Delta ^{*}:Q\times \Sigma ^{*}\rightarrow 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 }$.

Словами, ${\displaystyle \Delta ^{*}(r,x)}$ является множеством всех состояний, достижимых из состояния ${\displaystyle r}$ при получении строки ${\displaystyle x}$. Строка ${\displaystyle w}$ принимается, если некоторое конечное состояние из ${\displaystyle F}$ может быть достигнуто из начального состояния ${\displaystyle q_{0}}$ для входной строки ${\displaystyle w}$^[11][12].

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

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

Пример

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

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

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

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

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

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

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

• Если рассмотреть первое из формальных определений выше, строка «1011» принимается, поскольку при её чтении ${\displaystyle M}$ может пройти последовательность состояний ${\displaystyle \langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle }$, которая удовлетворяет условиям 1-3.
• Если рассмотреть второе из формальных определений, проход снизу вверх показывает, что ${\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\}}$, строка «1011» принимается.

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

Эквивалентность ДКА

Детерминированный конечный автомат (ДКА, англ. Deterministic finite automaton, DFA) можно рассматривать как специальный вид НКА, в котором для любого состояния и букв алфавита функция перехода имеет лишь одно результирующее состояние. Таким образом ясно, что любой формальный язык, который можно распознать с помощью ДКА, можно распознать и с помощью НКА.

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

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

НКА с ε-переходами

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

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

НКА-ε формально представляется 5-кортежем, ${\displaystyle (Q,\Sigma ,\Delta ,q_{0},F)}$, который состоит из:

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

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

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

Для состояния ${\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},\epsilon )}$ для любых ${\displaystyle 1\leqslant i<k}$
• ${\displaystyle q_{k}=p}$.

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

ε-замыкание определяется также для множества состояний. ε-замыкание множества состояний, ${\displaystyle P}$, НК-автомата определяется как множество состояний, достижимых из элементов множества ${\displaystyle P}$ по ε-переходам. Формально, для ${\displaystyle P\subseteq QE(P)=\cup _{q\in P}E(q)}$.

Принимаемые состояния

Пусть ${\displaystyle w=a_{1}a_{2}...a_{n}}$ будет строкой над алфавитом ${\displaystyle \Sigma }$. Автомат ${\displaystyle M}$ принимает строку ${\displaystyle w}$, если существует последовательность состояний ${\displaystyle r_{0},r_{1},...,r_{n}}$ в ${\displaystyle Q}$ со следующими условиями:

1. ${\displaystyle r_{0}\in E(q_{0})}$
2. ${\displaystyle r_{i+1}\in E(r')}$, где ${\displaystyle r'\in \Delta (r_{i},a_{i+1})}$ для любого ${\displaystyle i=0,...,n-1}$
3. ${\displaystyle r_{n}\in F}$.

Словами. Первое условие говорит, что машина начинает с состояния, которое достижимо из состояния ${\displaystyle q_{0}}$ по ε-переходам. Второе условие говорит, что после чтения ${\displaystyle a_{i}}$ машина выбирает переход ${\displaystyle \Delta }$ из ${\displaystyle r_{i}}$ в ${\displaystyle r'}$, а затем осуществляет любое число ε-переходов согласно ${\displaystyle \Delta }$ для перехода из ${\displaystyle r'}$ в ${\displaystyle r_{i+1}}$. Последнее условие говорит, что машина принимает ${\displaystyle w}$, если последний входной символ приводит к переходу машины в одно из принимаемых состояний. В противном случае говорят, что автомат отвергает строку. Множество строк, которые ${\displaystyle M}$ принимает, является языком, который распознаёт автомат ${\displaystyle M}$, и этот язык обозначается как ${\displaystyle L(M)}$.

Пример

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

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

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

Вход Состояние	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

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

Эквивалентность НКА

Чтобы показать, что НКА-ε эквивалентен НКА, сначала обратим внимание на то, что НКА является частным случаем НКА-ε, остаётся показать, что для любого НКА-ε существует эквивалентный НКА.

Пусть ${\displaystyle A=(Q,\Sigma ,\Delta ,q_{0},F)}$ будет НКА-ε. НКА ${\displaystyle A'=(Q,\Sigma ,\Delta ',E(q_{0}),F)}$ эквивалентен ${\displaystyle A}$, где для любого ${\displaystyle a\in \Sigma }$ и ${\displaystyle q\in Q}$ ${\displaystyle \Delta '(q,a)=E(\Delta (q,a))}$.

Тогда НКА-ε эквивалентен НКА. Поскольку НКА эквивалентен ДКА, НКА-ε также эквивалентен ДКА.

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

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

Говорят, что НКА замкнут относительно (бинарной/унарной) операции. Если НКА распознаёт языки, которые получаются путём применения этой операции к распознаваемым автоматом НКА языкам. НКА замкнуты относительно следующих операций.

• Объединение (см. рисунок)
• Пересечение
• Конкатенация
• Дополнение
• Замыкание Клини

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

НКА могут быть построены из любого регулярного выражения с помощью алгоритма Томпсона^[англ.].

Свойства

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

Множество всех строк, принимаемых НКА, является языком, который принимает НКА. Этот язык является регулярным языком.

Для любого НКА можно найти детерминированный конечный автомат (ДКА), который принимает тот же самый язык. Поэтому есть возможность преобразовать существующий НКА в ДКА с целью реализации (возможно) более простой машины. Такое преобразование осуществляется с помощью конструкцией подмножеств^[англ.], которое может вести к экспоненциальному увеличению числа необходимых состояний. Для формального доказательства конструкции подмножеств см. статью «Конструкция подмножеств^[англ.]».

Реализация

НКА можно моделировать одним из следующих способов:

• Преобразование в эквивалентный ДКА. В некоторых случаях это может привести к взрывному росту числа состояний^[14].
• Поддержание множества всех состояний, в которых НКА может оказаться после чтения слова. При обработке входного символа необходимо объединить результаты функции переходов, применённой к текущему множеству состояний, чтобы получить следующее множество. Если разрешены ε-переходы, нужно также включить все состояния, достижимые по таким переходам (ε-замыкание). Каждый шаг требует не более ${\displaystyle s^{2}}$ вычислений, где s — число состояний НКА. Автомат принимает строку если и только если при обработке последнего входного символа, одно из текущих состояний является конечным. Строка длины n может быть обработана за время O(ns²)^[15] с использованием O(s) памяти.

Приложения НКА

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

См. также

• Детерминированный конечный автомат
• Двухсторонний недетерминированный конечный автомат^[англ.]
• Автомат с магазинной памятью
• Машина Тьюринга

Примечания

1. Martin, 2010, с. 108.
2. Rabin, Scott, 1959, с. 114–125.
3. Последовательность выборов может привести в «тупик», в котором ни один из переходов неприменим для текущего входного символа и это случай считается неудачей (строка отвергается).
4. Hopcroft, Ullman, 1979, с. 19.
5. Aho, Hopcroft, Ullman, 1974, с. 319.
6. Hopcroft, Ullman, 1979, с. 19—20.
7. Sipser, 1997, с. 48.
8. Hopcroft, Motwani, Ullman, 2001, с. 56.
9. Aho, Hopcroft, Ullman, 1974, с. 320.
10. Sipser, 1997, с. 54.
11. Hopcroft, Ullman, 1979, с. 21.
12. Hopcroft, Motwani, Ullman, 2001, с. 59.
13. Finite-State Machine FOLDOC Free Online Dictionary of Computing  (неопр.). Дата обращения: 11 февраля 2020. Архивировано 4 апреля 2015 года.
14. Chris Calabro. NFA to DFA blow up. 2005-02-27  (неопр.). Дата обращения: 11 февраля 2020. Архивировано 7 февраля 2013 года.
15. Hopcroft, Motwani, Ullman, 2001, с. 153.

Литература

• Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. — Reading/MA: Addison-Wesley, 1974. — ISBN 0-201-00029-6.
  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — Москва: «Мир», 1979.
• John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. — Reading/MA: Addison-Wesley, 1979. — ISBN 0-201-02988-X.
  • John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation. — 2. — Addison Wesley, 2001. — ISBN 0-201-44124-1.
  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.
• Michael Sipser. Introduction to the Theory of Computation. — Boston/MA: PWS Publishing Co., 1997. — ISBN 0-534-94728-X.
• John Martin. Introduction to Languages and the Theory of Computation. — McGraw Hill, 2010. — ISBN 978-0071289429.
• Rabin M. O., Scott D. Finite Automata and Their Decision Problems // IBM Journal of Research and Development. — 1959. — Апрель (т. 3, вып. 2). — doi:10.1147/rd.32.0114.
• Allan C., Avgustinov P., Christensen A. S., Hendren L., Kuzins S., Lhoták O., de Moor O., Sereni D., Sittampalam G., Tibble J. Adding trace matching with free variables to AspectJ // In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications. — San Diego, CA, USA: OOPSLA '05. ACM, New York, NY, 2005. — С. 345—364. Архивная копия от 18 сентября 2009 на Wayback Machine