3
(я нашел ответ, его ниже в комментариях к кому-либо еще)время сложность торговли офф НЛА против DFA
Ищу обсуждение, на котором лучше использовать и в каком circumstanes в компиляторе НКА или DFA. какова временная сложность компромиссов для моделирования nfa vs dfa и какая из них более подходит при каких обстоятельствах в компиляторе?
Спасибо им пересмотреть для экзамена колледжа и помощь будет значительно apriciated :)
Leanne. кто-нибудь ответит мне :(:)
я нашел ответ для всех, кто хочет .. – user560618
Цели времени-пространства: Цель рег. exp.r и input stringx, определить, является ли x в L (r). Метод № 1: Сборка NFAN fromr с использованием конструкции Томпсона, затем запустить предыдущий алгоритм. Можно построить время NFA inO (| r |). ¡N имеет не более чем вдвое большее число состояний, чем | r |, и не более двух переходов из каждого состояния, поэтому таблица перехода - это пространство O (| r |). ¡Предыдущий алгоритм принимает или отклоняет x inO (| r | × | x |) time – user560618
Метод №2: постройте NFAN fromr, используя конструкцию Томпсона, затем DFAD fromN с использованием построения подмножества; затем используйте алгоритм DFA с последнего момента принятия/отклонения ¡D может иметь до 2k состояний, где k = # состояний в N. «Строка наихудшего случая» (a | b) * a (a | b) (a | b) ... (a | b): почему? ¡Алгоритм принятия DFA принимает или отклоняет x inO (| x |) – user560618