Механизмы DFA и NFA: в чем разница их возможностей и ограничений?

Детерминированные конечные автоматы (DFA) и недетерминированные конечные автоматы (NFA) имеют точно такие же возможности и ограничения. Единственная разница заключается в удобстве записи.

Конечный автомат — это процессор, который имеет состояния и считывает ввод, причем каждый входной символ потенциально переводит его в другое состояние. Например, состояние может быть «только что прочитал две буквы C подряд» или «начинаю слово». Обычно они используются для быстрого сканирования текста для поиска шаблонов, например, для лексического сканирования исходного кода, чтобы превратить его в токены.

Детерминированный конечный автомат находится в одном состоянии в каждый момент времени, что реализуемо. Недетерминированный конечный автомат может находиться более чем в одном состоянии одновременно: например, в языке, где идентификаторы могут начинаться с цифры, может быть состояние «чтение числа» и другое состояние «чтение идентификатора», а также NFA может быть в обоих одновременно при чтении чего-либо, начинающегося с «123». Какое состояние на самом деле применяется, будет зависеть от того, встретило ли оно что-то нечисловое перед концом слова.

Теперь мы можем выразить «чтение числа или идентификатора» как само состояние, и вдруг нам не понадобится NFA. Если мы выразим комбинации состояний в NFA как сами состояния, мы получим DFA с гораздо большим количеством состояний, чем NFA, но который делает то же самое.

Вопрос в том, что легче читать, писать или с чем иметь дело. DFA легче понять сами по себе, но NFA, как правило, меньше.

Вот нетехнический ответ от Microsoft:

Механизмы DFA работают за линейное время, потому что они не требуют обратного отслеживания (и, следовательно, они никогда не проверяют один и тот же символ дважды). Они также могут гарантировать соответствие максимально длинной строке. Однако, поскольку механизм DFA содержит только конечное состояние, он не может сопоставить шаблон с обратными ссылками, а поскольку он не создает явного раскрытия, он не может захватывать подвыражения.

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

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

Программисты предпочитают традиционные механизмы NFA, потому что они более выразительны, чем механизмы DFA или POSIX NFA. Хотя в худшем случае они могут работать медленно, вы можете настроить их так, чтобы они находили совпадения за линейное или полиномиальное время, используя шаблоны, которые уменьшают неоднозначность и ограничивают поиск с возвратом.

[http://msdn.microsoft.com/en-us/library/0yzc2yb0.aspx]

Простое нетехническое объяснение, перефразированное из книги Джеффри Фридла Mastering Regular Expressions.

ВНИМАНИЕ:

Хотя эта книга обычно считается «библией регулярных выражений», возникают некоторые разногласия относительно того, действительно ли правильно проведенное здесь различие между DFA и NFA. Я не ученый-компьютерщик, и я не понимаю большую часть теории, лежащей в основе того, что на самом деле является «регулярным» выражением, детерминированным или нет. После того, как разгорелся спор, я удалил этот ответ из-за этого, но с тех пор на него ссылаются в комментариях к другим ответам. Мне было бы очень интересно обсудить это дальше — неужели Фридль действительно ошибается? Или я неправильно понял Фридла (но я перечитал эту главу вчера вечером, и это точно так же, как я вспомнил...)?

Редактировать: Похоже, мы с Фридлом действительно ошиблись. Пожалуйста, ознакомьтесь с отличными комментариями Эймона ниже.

Исходный ответ:

Подсистема DFA проходит через входную строку символ за символом и пробует (и запоминает) все возможные способы совпадения регулярного выражения на данном этапе. Если он достигает конца строки, он объявляет успех.

Представьте строку AAB и регулярное выражение A*AB. Теперь мы пройдемся по нашей строке буква за буквой.

1. A:

   • First branch: Can be matched by A*.
   • Вторая ветвь: можно сопоставить, игнорируя A* (допускаются нулевые повторения) и используя второй A в регулярном выражении.

2. A:

   • First branch: Can be matched by expanding A*.
   • Вторая ветвь: Не может быть сопоставлена ​​с B. Вторая ветвь не работает. Но:
   • Третья ветвь: можно сопоставить, не расширяя A* и используя вместо этого вторую A.

3. B:

   • First branch: Can't be matched by expanding A* or by moving on in the regex to the next token A. First branch fails.
   • Третья ветвь: Можно сопоставить. Ура!

Механизм DFA никогда не выполняет возврат в строке.

Подсистема NFA проходит через токен regex за токеном и пробует все возможные перестановки в строке, при необходимости откатываясь назад. Если он достигает конца регулярного выражения, он объявляет об успехе.

Представьте себе ту же строку и то же регулярное выражение, что и раньше. Теперь мы проходим через наш токен регулярного выражения за токеном:

1. A*: Сопоставьте AA. Запомните позиции возврата 0 (начало строки) и 1.
2. A: Не совпадает. Но у нас есть обратная позиция, к которой мы можем вернуться и попробовать еще раз. Механизм регулярных выражений отступает на один символ. Теперь A совпадает.
3. B: Совпадает. Достигнут конец регулярного выражения (остается одна свободная позиция возврата). Ура!

И NFA, и DFA являются конечными автоматами, как следует из их названий.

Оба могут быть представлены как начальное состояние, состояние успеха (или принятия) (или набор состояний успеха) и таблица состояний со списком переходов.

В таблице состояний DFA каждый ключ <state₀, input> будет переходить к одному и только одному state₁.

В таблице состояний NFA каждый <state₀, input> будет переходить в набор состояний.

Когда вы берете DFA, сбрасываете его в начальное состояние, задаете ему последовательность входных символов, и вы точно будете знать, в каком конечном состоянии он находится, и является ли это состоянием успеха или нет.

Однако когда вы берете NFA, он будет для каждого входного символа искать набор возможных состояний результата и (теоретически) случайным образом, недетерминировано, выбирать одно из них. Если существует последовательность случайных выборок, которая приводит к одному из состояний успеха для этой входной строки, то говорят, что NFA завершился успешно для этой строки. Другими словами, вы должны притворяться, что он волшебным образом всегда выбирает правильный.

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

Для тех, кто интересуется, как реальный, не волшебный механизм NFA может волшебным образом выбирать правильное состояние преемника для данного символа, эта страница описывает два распространенных подхода.

Я считаю объяснение, данное в Regular Expresss, The Complete Tutorial Яном Гойвартсом, наиболее полезным. См. стр. 7 этого PDF-файла:

https://www.princeton.edu/~mlovett/reference/Regular-Expressions.pdf

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