Плюсове и минуси на NFA в сравнение с DFA?

Предимства на NFA пред DFA: представянето използва по-малко памет.

Недостатъци на NFA в сравнение с NFA: По-бавно достигане до отговор.

Има ли други предимства или недостатъци?


algorithm default theory nfa
person crowso    schedule 04.02.2011    source източник
comment
Компромис между памет и скорост? Това е нечувано!   -  person Matti Virkkunen    schedule 04.02.2011
comment
Въпреки факта, че не знам какво означава nfa или в какъв контекст се използва: Имате нужда от нещо, с което да сравните. използва по-малко памет, за да го представи не е валидно твърдение, ако не го сравните с нещо друго.   -  person Felix Kling    schedule 04.02.2011
comment
@Felix Kling NFA = недетерминиран краен автомат   -  person Foo Bah    schedule 04.02.2011

Отговори (2)


arrow_upward
8
arrow_downward

Мисля, че доста добре разбрахте основните компромиси. NFA могат да бъдат по-ефективни в паметта, защото могат да кодират O(2n) различни конфигурации в O(n) пространство, докато DFA за същия език може да заема експоненциално пространство. Също така сте прави, че NFA имат по-бавни актуализации; повечето алгоритми за симулиране на NFA отнемат O(n) време за изчисляване на преходите на състоянията (където n е броят на състоянията) срещу O(1) време за DFA.

Има няколко други разлики между двете. Като начало, DFA обикновено са по-лесни за кодиране, тъй като за всяка двойка състояние и символ има точно един преход. Това естествено се поддава на многоизмерен масив за таблица на прехода. Обратно, NFA (или по-лошо, -NFA) обикновено изисква по-сложно представяне, тъй като може да има голям брой преходи за всяко състояние. Но NFA имат предимството, че много трансформации от сложни структури към автомати са по-прости с NFA. Например, каноничната конструкция на съвпадащ автомат от регулярен израз генерира -NFA, а не DFA, тъй като трансформацията се изразява най-добре чрез рекурсивно изграждане на по-малки -NFA и след това свързването им заедно с помощта на -движения. Възможно е директно да конвертирате регулярния израз в DFA, но това е значително по-трудно. По подобен начин много алгоритми за генериране на LR(k) парсери могат да бъдат по-интуитивно мотивирани чрез изследване как работи автоматът за разпознаване на манипулатори по отношение на NFA, а по-скоро по отношение на DFA (въпреки че повечето алгоритми за генериране на тези анализатори отиват директно към DFA, а не към NFA ).

Надявам се това да помогне!

person templatetypedef    schedule 04.02.2011

arrow_upward
1
arrow_downward

NFA представянията са по-компактни, но DFA са по-лесни за симулиране. Често има експоненциално увеличение на размера, когато NFA се намали до DFA

person Foo Bah    schedule 04.02.2011