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

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

Источник

5 ответов

Решение

Детерминированные конечные автоматы (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]

Источник

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

ВНИМАНИЕ:

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

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

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

Механизм 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: Матчи. Достигнут конец регулярного выражения (с одной резервной позицией возврата). Ура!
Источник

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

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

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

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

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

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

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

Источник

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

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

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

Источник
Другие вопросы по тегам