Можно ли сказать, что DFA более эффективен, чем NFA?

13

Я только начал читать о теории вычислений. Если мы сравним, что является более мощным (в принятии строк), оба одинаковы. Но как насчет эффективности? DFA будет быстрым по сравнению с NFA, поскольку у него есть только один исходящий фронт, и не будет никакой двусмысленности. Но в случае NFA мы должны проверить все возможные случаи, и это, безусловно, требует времени. Можно ли сказать, что DFA более эффективен, чем NFA?

Но моя другая часть мозга также думает, что NFA существует только в теории, поэтому мы не можем сравнить его эффективность с DFA.

finite-automata efficiency nondeterminism AVI
источник

16

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

Компактность представления

Говорить больше с меньшими затратами : НФА более эффективны.

Преобразование DFA в NFA является простым и не увеличивает размер представления.

Тем не менее, существуют обычные языки, для которых самый маленький DFA экспоненциально больше, чем самый маленький NFA. Типичным примером является для $(a|b)^*b(a|b)^k$ $k$ фиксированного .

вычисление

Быстрое выполнение : DFAs более эффективны.

Компьютеры, которые мы используем сегодня, имеют детерминированный характер. Это делает их плохими в борьбе с недетерминизмом. Существует два распространенных способа детерминистического обращения с NFA: возврат с одной стороны, что довольно дорого, или отслеживание активных состояний, что означает, что каждый переход займет в раз больше времени (где - размер NFA) , $N$ $N$

Khaur
источник

Что касается компактности, NFA не всегда более эффективны! Это правда, что есть языки, для которых минимальный DFA экспоненциально больше, чем самый компактный NFA, но какова доля таких языков в наборе всех языков?

saadtaame

2

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

Хаур

2

-1 "увеличение его размера (потенциально много)". Имитация наборов состояний NFA путем сохранения пространства затрат связанного списка не более

в числе состояний NFA. Эквивалентный DFA, с другой стороны, может иметь

состояний.

O (N)

$O(N)$

O (2^{N})

$O(2^N)$

Блуждающая логика

@WanderingLogic Вы правы, преобразование не обязательно должно быть явным (вы все еще используете эквивалентный DFA, только не в расширенной форме). Тем не менее, главный вопрос остается в силе, поскольку для этого требуется в

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

O (N)

$O(N)$

Хаур

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

6005

4

$n$ $2^n$

Соответствие DFA является линейным по размеру входной строки. Сопоставление NFA включает в себя возвратный контроль, поэтому NFA выполняют больше работы. Таким образом, DFAs являются более эффективными.

saadtaame
источник

Но можем ли мы сказать, что DFA более эффективен?

Ави

1

@avi Я редактировал вопрос! И, кстати, NFA не существуют только в теории: проверьте это: swtch.com/~rsc/regexp/regexp1.html

saadtaame

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

Питер

@Peter, что DFA больше, не имеет значения: это просто означает, что массив, дающий функцию перехода, больше.

vonbrand

1

@ Хаур, правда. Но если вы попали в этот вид проблемы, у вас есть Humongous DFA.

vonbrand

2

Просто добавив к ответам выше:

NFA могут быть вычислительно более эффективными, чем DFA, в том смысле, что их можно моделировать на параллельном процессоре.

Кстати, я вижу людей, которые говорят, что НФА не могут существовать в реальности. Позволю себе не согласиться. Компьютер с большим количеством процессоров может выполнять множество задач параллельно и может рассматриваться как недетерминированный компьютер. Можно назначить каждую ветвь вычислений новому процессору и остановить их все, когда один из них примет это.

Без названия
источник

1

Ни DFA, ни NFA не существуют в реальности, оба являются просто математическими отношениями, и оба могут быть смоделированы алгоритмами.

jmite

1

Если вы используете чисто теоретическое «количество шагов, чтобы принять / отклонить» меру, DFA всегда будет дешевле, чем NFA, который использует $\epsilon$ -переходы. Для более сложных автоматов такая мера будет иметь значение.

vonbrand
источник

Кто сказал, что вы должны использовать

ϵ

$\epsilon$ -переходы?

Хаур

1

@ Хаур, никто не сделал. Просто добавлено для полноты (я знаю, что вы можете избавиться от всего

ϵ

$\epsilon$ -переходы в НФА).

vonbrand

но не свободны ли DFA от ϵ-переходов?

Ави

@avi, да. Не стесняйтесь редактировать ответ, если там неясно.

vonbrand

нет я тебя спрашиваю Я тоже не уверен в этом

avi

1

Как уже отмечали другие, вы должны определить, что означает «эффективность». Чтобы проиллюстрировать это, я приведу разумную модель с другим ответом.

Смотреть только на автоматическую модель (модели), которая игнорирует, в частности, то, как вы реализуете их на реальных машинах, очевидным показателем эффективности является «число переходов, выполненных за (самый короткий) цикл принятия».

Что касается этой меры, обе модели автоматов эквивалентны , так как обе принимают ровно один переход на входной символ (wlog у нас нет $\varepsilon$ -переходы). Обратите внимание, что размер рассматриваемых автоматов здесь не учитывается.

Рафаэль
источник

1

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

Кроме этого, я согласен с Рафаэлем, что это очень сильно зависит от эффективности и реализации.

A.Schulz
источник

-4

Как мы знаем об автоматах, то есть машинах, которые могут выполнять любые действия без какой-либо силы человека или без непосредственного участия человека. Например: стиральная машина. Конечные автоматы означают, что мы знаем состояние выполнения задачи на машине, например: 1 нажмите кнопку ON, 2 нажмите кнопку OFF, так что есть только 2 состояния, т.е. они называются конечными автоматами. Теперь перейдем к DFA, т.е. к детерминированным конечным автоматам. формально это означает, что мы можем легко определить состояния, в которых нет двусмысленности, и неофициально для этого требуется только 1 переход, разрешенный на 1 символ. NFA: недетерминированные конечные автоматы. необходимо больше времени для вычисления фактического состояния, и существует неоднозначность, и неофициально говорится, что существует несколько разрешенных переходов на 1 символ. в случае времени для достижения пункта назначения NFA требует больше времени, чем DFA, но NFA может загрузить больше данных, чем DFA. * DFA и NFA имеют одинаковую силу для распознавания строки. спасибо .. дипали каушик

Дипали Каушик
источник

1

Конечные автоматы не имеют ничего общего со стиральными машинами.

Дэвид Ричерби

2

@DavidRicherby. Возможно, фраза «вообще ничего» немного сильна. В конце концов, можно сказать, что стиральная машина имеет состояния готовности , стирки , полоскания и отжима с соответствующими переходами между состояниями. Лучшей метафорой, однако, был бы управляемый монетой торговый автомат содовой.

Рик Декер

1

@RickDecker Согласен, но тратить время на обсуждение крошечной значимости было бы примером того, что Википедия называет « неоправданным весом ». И, в любом случае, часть ответа, о котором я говорю, - это обсуждение автоматов как автономных машин, а не вычислительных устройств.

Дэвид Ричерби

1

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

Рафаэль

Tho other answers almost exhaust everything to be said and unfortunately your answer is slightly confusing.

Evil

Можно ли сказать, что DFA более эффективен, чем NFA?

Ответы:

Компактность представления

вычисление