3
(i fand die Antwort, seine unten in den Kommentaren für alle anderen)Zeitkomplexität Abwägungen von nfa vs DFA
ich suche nach einer Diskussion auf dem besser genutzt und in welcher circumstanes in einem Compiler eine nfa oder dfa. Was ist die Zeit Komplexität Kompromisse von der Simulation eines NFA vs dfa und welche ist besser geeignet unter welchen Umständen in einem Compiler?
Vielen Dank, im für eine College-Prüfung und Hilfe revidieren würde :)
Leanne stark apriciated werden. jemand antwortet mir :(:)
fand ich die Antwort für jemand anderen suchen .. – user560618
Time-Space-Tradeoffs Ziel: Gegebene reg. exp.r und input stringx, bestimmen, obx in L (r) ist Methode Nr. 1: Erstellen Sie NFAN fromr unter Verwendung der Thompson-Konstruktion, führen Sie dann den vorherigen Algorithmus aus ¡Kann NFA inO (| r |) -Zeit konstruieren. ¡N hat höchstens doppelt so viele Zustände wie | r | und höchstens zwei Übergänge von jedem Zustand, so dass die Übergangstabelle isO (| r |) ist. ¡Vorheriger Algorithmus akzeptiert oder ablehntx inO (| r | x | x |) Zeit – user560618
Methode # 2: Baue NFAN fromr unter Verwendung der Thompson-Konstruktion, dann DFAD von N unter Verwendung der Subset-Konstruktion; Verwenden Sie dann den DFA-Algorithmus von letzter Zeit für das Akzeptieren/Ablehnen ¡D kann bis zu 2k Zustände haben, wobei k = # in N steht. '' Worst- Case '' Zeichenfolge (a | b) * a (a | b) (a | b) ... (a | b): Warum? ¡DFA-Akzeptanzalgorithmus akzeptiert oder ablehntx inO (| x |) – user560618