Двигатели DFA и NFA: в чем разница между их возможностями и ограничениями?

Question

Я ищу нетехническое объяснение различия между двигателями DFA и NFA, основанное на их возможностях и ограничениях.

Answer 1

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

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

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

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

Это вопрос, который легче читатьили пиши или разберись.Сами по себе DFA легче понять, но NFA, как правило, меньше.

Answer 2

Вот нетехнический ответ от 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]

Answer 3

Простое нетехническое объяснение, перефразированное из книги Джеффри Фридла Освоение регулярных выражений .

CAVEAT

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

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

---

Оригинальный ответ:

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

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

1. A:

   • Первая ветвь: может соответствовать A*.
   • Вторая ветвь: можно сопоставить, игнорируя A* (допускается ноль повторений) и используя второе A в регулярном выражении.

2. A

   • Первая ветвь: можно сопоставить, расширив A*.
   • Вторая ветвь: не может быть сопоставлено B. Вторая ветка терпит неудачу. Но:
   • Третья ветвь: можно сопоставить, если не расширять A* и использовать вместо нее вторую A.

3. B

   • Первая ветвь: не может быть сопоставлена ​​расширением A* или перемещением в регулярном выражении к следующему токену A. Первая ветка терпит неудачу.
   • Третья ветвь: может быть сопоставлена. Ура!

Двигатель DFA никогда не возвращается в строку.

---

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

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

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

Answer 4

Как говорят их имена, и NFA, и DFA являются конечными автоматами.

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

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

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

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

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

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

Answer 5

Я считаю объяснение, данное в Регулярных выражениях, The Complete Tutorial Яном Гойваэртом, наиболее пригодным для использования.См. Стр. 7 этого документа PDF:

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

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