Недетерминированные конечные автоматы в разработке программного обеспечения?

Question

Недавно я думал о конечных автоматах (FSM) и о том, как бы я реализовал их в программном обеспечении (язык программирования не имеет значения).

Насколько я понимаю, детерминированные автоматы широко используются (парсеры / лексеры, компиляторы и т. Д.), Но что случилось с недетерминированными машинами состояний ?

Я знаю, что возможно преобразовать все недетерминированные конечные автоматы в детерминированные (даже программно). Это не моя точка зрения. Я также представляю, что недетерминированные конечные автоматы гораздо сложнее реализовать.

В любом случае, имеет ли смысл любой смысл реализовывать недетерминированный конечный автомат? Есть ли какие-то специальные приложения, о которых я не знаю? Какие могут быть причины для этого? Может быть, оптимизированные и специализированные недетерминированные автоматы быстрее?

Answer 1

Большинство механизмов регулярных выражений используют не -детерминированные автоматы, поскольку они предлагают гораздо большую гибкость. DFAs гораздо более ограничены. Посмотрите на некоторые реализации, и вы увидите это. Microsoft даже подчеркивает этот факт в своей документации .NET Regex class:

Механизм регулярных выражений .NET Framework представляет собой средство сравнения регулярных выражений с обратным отслеживанием, которое включает в себя традиционный недетерминированный механизм конечных автоматов (NFA), такой как используемый Perl, Python, Emacs и Tcl.

Соответствующее поведение (первый абзац) - эта статья также предлагает обоснование использования NFA, а не более эффективного DFA.

Answer 2

Как вы знаете, NFA и DFA в вычислительном отношении эквивалентны. Это одна из первых теорем в теории автоматов. Существуют алгоритмы для преобразования одного в другое (в отличие от Pushdown или машин Тьюринга).

Итак. Почему один над другим? Потому что представление данной проблемы с NFA намного проще, чем с эквивалентным DFA.

edit: с точки зрения фактического вычисления машины, DFA будут работать быстрее, потому что им не нужно возвращаться. Но они потребуют больше памяти, чтобы представлять. (Mem против ЦП)

Answer 3

Мой совет = взгляните на руководство по Адриан Терстонс Рэгел .

Существуют простые способы генерирования DFA напрямую, но я считаю, что они поддерживают только ограниченный круг операторов - в основном, как подозревает EBNF. Ragel использует недетерминированные методы для составления сложных автоматов из более простых, а затем использует удаление и минимизацию эпсилонов для создания эффективных детерминированных автоматов. Независимо от того, сколько странных операторов вам нужно, преобразование в минимальные детерминированные автоматы всегда одинаково, и каждая реализация оператора остается простой с помощью недетерминированных методов.

Answer 4

Я думаю, что основной причиной выбора недетерминированного конечного автомата будет фактическое возвращение выбранного соответствия. Вероятно, намного сложнее сделать это с детерминированной версией.

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

Answer 5

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

Answer 6

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

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

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

Answer 7

Алгоритм Витерби работает на Скрытых марковских моделях , рассматривая их так же, как NFA. Не совсем идентично, но, безусловно, аналогично.

Они полезны в таких приложениях, как распознавание речи и текста.

Answer 8

Cayuga использует недетерминированные конечные автоматы под колпаком для обработки сложных событий. Ну, похоже, они называют это «публикацией / подпиской с отслеживанием событий», но я считаю, что это CEP.

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

... автоматы Каюги, расширенные от стандартных недетерминированных конечных автоматов.