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

НКА для .
ДКА для этого языка имеет по меньшей мере 16 состояний.

Конечный автомат называется детерминированным (ДКА, англ. deterministic finite automaton, DFA), если

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

От недетерминированного конечного автомата (НКА, англ. nondeterministic finite automaton, NFA) выполнение этих ограничений не требуется. В частности, любой ДКА является также НКА.

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

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

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

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

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

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

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

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

АвтоматыПравить

НКА формально представляется как 5-кортеж  , состоящий из

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

Здесь   означает степень множества  .

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

Если дан НКА  , он распознаёт язык, который обозначается как  , и который определяется как множество всех строк над алфавитом  , принимаемых автоматом  .

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

  •   принимается, если существует последовательность состояний   в  , такая что
    1.  
    2.  , для  
    3.  .
Словами. Первое условие гласит, что машина начинает работу из состояния  . Второе условие гласит, что для каждого символа строки   машина переходит из состояния в состояние согласно функции переходов  . Последнее условие гласит, что машина принимает строку  , если входная строка   приводит машину к завершению в конечном состоянии. Чтобы строка   была принята автоматом  , не требуется, чтобы любая последовательность состояний завершается в конечном состоянии, достаточно, чтобы в такое состояние приводила одна последовательность. В противном случае, то есть, если невозможно перейти из   в состояние из   следуя  , говорят, что автомат отвергает строку. Множество строк, которые автомат   принимает, является языком, распознаваемым автоматом  , и этот язык обозначается как  [9][10]
  • Альтернативно,   принимается, если  , где   определяется рекурсивно:
    1.  , где   является пустой строкой
    2.   для любого  .
Словами,   является множеством всех состояний, достижимых из состояния   при получении строки  . Строка   принимается, если некоторое конечное состояние из   может быть достигнуто из начального состояния   для входной строки  [11][12]

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

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

ПримерПравить

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

Следующий автомат   с двоичным алфавитом определяет, кончается ли входная строка единицей. Пусть  , где функция переходов   может быть определена следующей таблицей переходов состояний[en] (сравните с верхним рисунком слева):

Вход
Состояние
0 1
     
     

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

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

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

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

  • Если рассмотреть первое из формальных определений выше, строка «1011» принимается, поскольку при её чтении   может пройти последовательность состояний  , которая удовлетворяет условиям 1-3.
  • Если рассмотреть второе из формальных определений, проход снизу вверх показывает, что  , следовательно  , а тогда  , откуда  , и, наконец,  . Поскольку это множество содержит  , строка «1011» принимается.

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

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

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

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

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

НКА с ε-переходамиПравить

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

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

НКА-ε формально представляется 5-кортежем,  , который состоит из

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

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

Для состояния   пусть   означает множество состояний, достижимых из   следующими ε-переходами в функции переходов  , а именно,   если существует последовательность состояний  , таких что

  •  ,
  •   для любых  
  •  .

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

ε-Замыкание определяется также для множества состояний. ε-Замыкание множества состояний,  , НК-автомата определяется как множество состояний, достижимых из элементов множества   по ε-переходам. Формально, для  .


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

Пусть   будет строкой над алфавитом  . Автомат   принимает строку  , если существует последовательность состояний   в   со следующими условиями

  1.  
  2.  , где   для любого  
  3.  .

Словами. Первое условие говорит, что машина начинает с состояния, которое достижимо из состояния   по ε-переходам. Второе условие говорит, что после чтения   машина выбирает переход   из   в  , а затем осуществляет любое число ε-переходов согласно   для перехода из   в  . Последнее условие говорит, что машина принимает  , если последний входной символ приводит к переходу машины в одно из принимаемых состояний. В противном случае говорят, что автомат отвергает строку. Множество строк, которые   принимает, является языком, который распознаёт автомат  , и этот язык обозначается как  .

ПримерПравить

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

В формальных обозначениях, пусть  , где отношение переходов   может быть определено такой таблицей переходов состояний[en]:

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

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

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

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

Пусть   будет НКА-ε. НКА   эквивалентен  , где для любого   и    .

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

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

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

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

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

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

СвойстваПравить

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

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

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

РеализацияПравить

Имеется несколько способов реализации НКА:

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

Приложения НКАПравить

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

См. такжеПравить

ПримечанияПравить

  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-2-.
  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. FOLDOC Free Online Dictionary of Computing, Finite-State Machine
  14. http://cseweb.ucsd.edu/~ccalabro/essays/fsa.pdf
  15. Hopcroft, Motwani, Ullman, 2001, с. 153.
  16. Allan, Avgustinov, Christensen и др., 2005, с. 345-364.

ЛитератураПравить