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

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

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

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

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

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

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

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

Неформальное введение [ править ]

Есть несколько неформальных объяснений, которые эквивалентны.

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

Формальное определение [ править ]

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

Автомат [ править ]

НКА представлена формально в 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 \ substeq Q}$

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

Распознаваемый язык [ править ]

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

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

• ${\ displaystyle w}$принимается, если последовательность состояний существует в такой, что:${\ displaystyle r_ {0}, r_ {1}, ..., r_ {n}}$${\ displaystyle Q}$
  1. ${\ displaystyle r_ {0} = q_ {0}}$
  2. ${\ displaystyle r_ {я + 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}$accept - это язык, который распознается , и этот язык обозначается . ^{[5] : 320 [6] : 54}${\displaystyle M}$${\displaystyle L(M)}$

• В качестве альтернативы принимается, если , где определяется рекурсивно :${\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 }$

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

Исходное состояние [ править ]

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

Пример [ править ]

Следующий автомат с двоичным алфавитом определяет, заканчивается ли вход цифрой 1. Пусть функция перехода может быть определена этой таблицей переходов состояний (см. Верхний левый рисунок):${\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» принимается, поскольку при чтении оно может проходить через последовательность состояний , которая удовлетворяет условиям 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.

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

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

NFA с ε-ходами [ править ]

Недетерминированный конечный автомат с ε-движениями (NFA-ε) является дальнейшим обобщением на NFA. Этот автомат заменяет функцию перехода на ту, которая допускает пустую строку ε в качестве возможного входа. Переходы без использования входного символа называются ε-переходами. На диаграммах состояний они обычно обозначаются греческой буквой ε. ε-переходы обеспечивают удобный способ моделирования систем, текущие состояния которых точно не известны: т. е. если мы моделируем систему и неясно, должно ли текущее состояние (после обработки некоторой входной строки) быть 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},\varepsilon )}$для каждого , и${\displaystyle 1\leq i<k}$
• ${\displaystyle q_{k}=p}$.

${\displaystyle E(q)}$известен как е-закрытия в .${\displaystyle q}$

ε-замыкание также определено для набора состояний. Ε-замыкание набора состояний , NFA определяется как набор состояний, достижимых из любого состояния при следующих ε-переходах. Формально для определения .${\displaystyle P}$${\displaystyle P}$${\displaystyle P\subseteq Q}$${\displaystyle E(P)=\bigcup \limits _{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 w}$${\displaystyle M}$ ${\displaystyle M}$${\displaystyle L(M)}$

Пример [ править ]

Пусть будет NFA-ε с двоичным алфавитом, который определяет, содержит ли вход четное количество нулей или четное количество единиц. Обратите внимание, что 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 : один с состояниями, а другой с состояниями . Язык может быть описан регулярным языком, задаваемым этим регулярным выражением (1 * (01 * 01 *) *) ∪ (0 * (10 * 10 *) *). Мы определяем с помощью ε-движений, но их можно определить без использования ε-движений.${\displaystyle \{S_{1},S_{2}\}}$${\displaystyle \{S_{3},S_{4}\}}$${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$

Эквивалентность NFA [ править ]

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

Позвольте быть NFA-ε. НКА эквивалентно , где для каждого и , .${\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))}$

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

Свойства закрытия [ править ]

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

• Союз (см. Рисунок)
• Пересечение
• Конкатенация
• Отрицание
• Клини закрытие

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

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

Свойства [ править ]

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

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

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

Реализация [ править ]

Есть много способов реализовать NFA:

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

Применение NFA [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• М.О. Рабин и Д. Скотт, "Конечные автоматы и их проблемы принятия решений", 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.)