временные сложности компромиссы нфа против дфа

Question

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

Answer 1

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

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