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

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

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

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

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

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

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

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

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

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

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

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

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

Автоматы

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

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

Здесь $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 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$.

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

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

Пример

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

Следующий автомат $M$ с двоичным алфавитом определяет, кончается ли входная строка единицей. Пусть $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».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Свойства

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

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

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

Реализация

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

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

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

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

См. также

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

Литература

• 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