deterministischer aus nichtdet. Automaten

Archiv Komplexität von Algorithmen
#1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

#2

deterministischer aus nichtdet. Automaten
Kann mir jemand sagen, wie man einen deterministischen aus einem nichtdeterministischen Automaten baut (Aufgabe 12 TheoInf 2 WS 2003/2004)? Steht im Schöning auf Seite 33, verstehe ich aber nicht.

#3

stell dir es so vor: der nichtdeterministische automat wird von einem deterministischen simuliert.

die zustände dieses DFA sind alle zustandskombinationen, die im NDA überhaupt auftreten können. genau dann,wenn sich der NDA z.b. in den zuständen a, b und c gleichzeitig befindet, ist der entsprechende DFA im zustand ‘{a, b, c}’. die gleichzeitigkeit der zustände im NDA wird also durch spezielle zustände im DFA repräsentiert.

da sich der NDA in potenziell allen kombinationen befinden könnte, wird als ausgangsbasis die potenzmenge der zustandsmenge des NDA genommen. wenn sich dann der NDA in irgendeiner zustandskombination A befindet, bist du sicher, dass es einen zustand im DFA gibt, der A repräsentiert.

mal angenommen, der NDA befinde sich in den zuständen a, b und c, und kommt durch die eingabe x in die zustände a, b, e, f und g, dann bildest du zuerst die zustandsmengen in die repräsentierenden zustände im DFA ab (also ein zustand namens ‘{a, b, c}’ und einer namens ‘{a, b, e, f, g}’) und verbindest die zwei mit ner kante x.

#4

  1. gibt es z.B. bei einem ndet Automaten mit A, B und C als Zustand in der det. Variante zusaetzlich die Zustaende “A und B”, “A und C”, “B und C”, “A und B unc C”, Potenzmenge eben wie schon oben beschrieben. Endzustaende im ndet Zustand muss man auch beachten, weis aber nimmer sicher wie, aber so logisch gesehen wuerd ich sagen, sobald einer der korrelierenden Zustaende im ndet Automat Endzustand ist, ist der des det auch, das kriegst aber sicher im schoening raus.

  2. Malt man sich alle diese Zustaende eben mal hin.

  3. Nun musst du alle Zustandsuebergange des ndet Automatenin in den det Automaten einzeichnen, achtung, da kann ein Uebergang zu mehreren werden.

  4. nicht-erreichbare zustaende kann man am Ende wieder streichen

Ohne Garantie auf Korrektheit oder Vollstaendigkeit, ist schon a Zeit her, aber vielleicht ists jetzt ein bissl klarer.

#5

Ok danke!