DFA, NFA и epsilon NFA - все три позволяют нам представлять определенный регулярный язык. С любым из этих представлений мы можем прийти к одному и тому же регулярному выражению, тогда зачем нам нужно изучать все три формы представления конечных автоматов? Может быть какое-то объяснение того, что может сделать NFA, чего не может DFA, то есть NFA может помочь нам в разработке неопределенностей. Например, при разработке игры (шахматы) у нас есть много вариантов перемещения конкретной фигуры из определенного места, которая может быть легко представлена с помощью NFA. Но какая польза от эпсилона NFA, когда то же самое можно сделать с помощью NFA или DFA?
automata
finite-automata
education
Бхарат Банаваликар
источник
источник
Ответы:
Добавьте обычные грамматики для четвертого. Есть и другие ...
Регулярные выражения (а также регулярные грамматики) - это совершенно разные формализмы, которые описывают один и тот же набор языков. Опять же, доказательство этого факта исследует важные взаимосвязи и является примером того, что формализмы могут выглядеть очень разнообразными, основываться на принципиально разных понятиях, но описывать одни и те же языки. Опять же, в довольно простой обстановке.
Для использования в "реальном мире" вы можете начать с регулярного выражения и получить минимальный DFA для высокопроизводительного поиска. Цифровые схемы - это, по сути, DFA, понимание их занимает центральное место в компьютерной инженерии. Наконец, что не менее важно, часто системы могут быть смоделированы как «находящиеся в состоянии» и «переходящие в другое» при воздействии внешних раздражителей, даже если система очень далека от реального DFA, и ее просмотр таким образом может помочь понять ее.
Добавлено позже: Как отметил Рафаэль, может быть более эффективно интерпретировать NFA непосредственно для поиска, потому что создание DFA может быть дорогим, а NFA может быть намного меньше.
источник
существует множество причин для изучения различных форм / соответствий ДФА и НФА. Вот несколько выделенных моментов, некоторые из продвинутой теории сложности.
NFA - интересная модель для «параллельных вычислений». продвижение состояний через NFA можно рассматривать как параллельную версию вычисления DFA. поэтому вычисления DFA и NFA отражают некоторые различия между последовательными и параллельными вычислениями. Сравнивая оба контекста, он также помогает изучить сложную алгоритмическую сложность задач.
NFA часто используются в системах сопоставления регулярных выражений (довольно распространенных среди языков, особенно современных, появившихся в эпоху Unix), которые обычно допускают описания регулярных выражений, которые преобразуются в NFA, а затем, возможно, преобразуются в DFA для более эффективного поиска.
Есть довольно много открытых проблем, которые остаются в областях, и они часто изучаются на основе соответствия DFA / NFA. посмотрите, например, есть ли какие-либо открытые проблемы на DFA (cstheory stackexchange). несколько удивительно, что некоторые из них связаны с очень глубокими областями CS, включая проблему P против NP, то есть непрямость пересечения DFA . также другой открытой областью является, например, вычисление минимального NFA для DFA .
также для некоторого связанного понимания см. этот полуизвестный / высоко голосованный вопрос на cstheory.se : Какого просветления я должен достичь после изучения конечных автоматов?
Есть очень разнообразные применения ДФА против НФА, и в них часто используется соответствие между ними. Соответствие строковому шаблону упоминалось выше, но конструкции DFA / NFA часто используются в (автоматическом) распознавании речи. см., например, этот цитируемый документ: Взвешенные датчики конечного состояния в распознавании речи / Мохри, Перейра, Райли
источник
DFA имеют более простую реализацию, чем NFA, поскольку их следующее состояние определяется функцией, а NFA помогают пользователю легко выразить то, что он хочет, в качестве выходных данных, поскольку NFA может выбирать между несколькими путями. и epsilon-NFA является расширением NFA, где переходы могут выполняться без ввода каких-либо входных символов.
источник
В числе штатов ДФА есть неприятная вещь. Иногда взрывается .
Короче говоря, если число состояний просто слишком велико (все еще конечно, но мы живем в физическом мире), то вам придется повысить уровень абстракции, чтобы справиться со сложностью за счет некоторого замедления. Другие модели, такие как NFA и AFA, должны предоставлять более сжатые способы представления обычных языков.
источник