Компромиссы временной сложности nfa против dfa

Я ищу обсуждение того, что лучше использовать и при каких обстоятельствах в компиляторе nfa или dfa. каковы компромиссы временной сложности при моделировании nfa и dfa и какой из них более подходит при каких обстоятельствах в компиляторе??


time time-complexity compiler-construction dfa nfa
person Lilly_Code    schedule 02.01.2011    source источник
comment
я нашел ответ для всех, кто ищет ..   -  person Lilly_Code    schedule 10.01.2011
comment
Компромиссы между временем и пространством Цель: Учитывая рег. exp.r и входная строка x, определите, находится ли x в L(r) Метод №1: Постройте NFAN из r, используя конструкцию Томпсона, затем запустите предыдущий алгоритм ○ Может построить NFA за время O(|r|). ¡ N имеет не более чем в два раза больше состояний, чем |r|, и не более двух переходов из каждого состояния, поэтому таблица переходов занимает O(|r|) пространства. ○ Предыдущий алгоритм принимает или отклоняетx через O(|r|×|x|) раз   -  person Lilly_Code    schedule 10.01.2011
comment
Метод № 2: построить NFAN из r, используя конструкцию Томпсона, затем DFAD из N, используя конструкцию подмножества; затем используйте алгоритм DFA из прошлого раза для принятия/отклонения x ¡ D может иметь до 2k состояний, где k = # состояний в N. Строка «наихудшего случая» (a |b)*a (a |b)(a |б)...(а |б) : почему? ○ Алгоритм принятия DFA принимает или отклоняетx inO(|x|)   -  person Lilly_Code    schedule 10.01.2011
comment
Резюме: Automaton Build Run NFA O(|r|) O(|r|×|x|) DFA O(2|r|) O(|x|) Поэтому используйте первый метод (NFA) для быстрого поиска по коротким текстовым строкам (например, emacs для поиска) Используйте второй метод (DFA) для более длительного поиска по длинным текстовым строкам (например, Unix grep для нескольких файлов) «Ленивый» метод DFA строит таблицу переходов DFA на лету, кэшируя переходы как состояние/ввод встречаются пары   -  person Lilly_Code    schedule 10.01.2011
comment
Я понимаю, что количество состояний в DFA, построенном из NFA с $r$ состояниями, может достигать $2^r$, но я не понимаю, какова стоимость построения DFA из NFA с $r$ состояниями. $ О (2 ^ г) $. Как насчет стоимости добавления ребер для каждого входного символа DFA? Является ли $O(вершин) = O(ребер)$ для построенного DFA?   -  person dhruvbird    schedule 25.11.2013

Ответы (1)


arrow_upward
3
arrow_downward

  • Время построения DFA из NFA составляет O (2 ^ m), где m — количество узлов.
  • Время выполнения DFA равно O(n), где n — длина входной строки. Это связано с тем, что для данной строки существует только 1 путь через DFA.
  • Время построения NFA должно быть O(m), где m — количество узлов.
  • Время выполнения NFA составляет O(m²n), потому что он недетерминирован, и компьютер должен проверять все возможные пути для текущего символа в строке. (если не смотреть вперед, он не знает, каким будет следующий символ, поэтому он заходит в тупик)

Эти цифры могут дать вам краткое представление

person Nihal Rp    schedule 31.08.2015
comment
Запуск NFA с возвратом, как вы, кажется, предполагаете, в худшем случае займет O (2 ^ n). К счастью, есть более умные алгоритмы, которые требуют O(mn) времени, хотя они и не поддерживают обратные ссылки. (Одна из реализаций — re2 от Google.) - person ; 31.08.2015