Преимущества / недостатки NFA перед DFA и наоборот

Question

Каковы относительные плюсы и минусы как DFA, так и NFA по сравнению друг с другом?

Я знаю, что DFA легче реализовать, чем NFA, и что NFA медленнее достигают состояния принятия, чем DFA, но есть ли другие явные, хорошо известные преимущества / недостатки?

Answer 1

Преимущество NFA перед DFA - это свойство всегда «выбирать правильный путь». Поскольку в алгоритме нельзя сказать «выбрать правильный путь», обычно выполняется преобразование из NFA в DFA, создавая состояния DFA, которые символизируют несколько состояний NFA. Таким образом, когда ваш NFA находится в состоянии A и может выбрать A, B или C, то следующим состоянием в вашем DFA будет {A, B, C}.

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

Answer 2

NFA и DFA принимают один и тот же набор языков - обычные языки.

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

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

Делая грубые обобщения, DFA быстрее, но более сложны (с точки зрения количества состояний).и переходы), тогда как НФА медленнее, но проще (в тех же терминах).

Answer 3

Одно определенное преимущество NFA перед DFA состоит в том, что вы можете легко создать FA, представляющий язык, который представляет собой объединение, пересечение, объединение и т. Д. Из двух (или более) языков, используя NFA. То есть, если у вас есть несколько простых FA, выполняющих часть работы, вы можете легко комбинировать их, используя NFA. При использовании DFA вам нужно создать новый автомат, выполняющий всю работу сам.

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