NFA zu DFA umwandeln, DFA minimieren und Sprache des NFA angeben (entspricht der des equivalenten DFA)

Question

Frage: NFA zu DFA umwandeln mit Potenzmengenkonstruktion (bzw. Myhill Konstruktion); resultierenden DFA minimieren sowie Sprache des NFA angeben (die equivalent mit der Sprache des minimalen DFA sein müsste)

Da keine handschriftlichen Uploads erlaubt ist die Frage eventuell zu umständlich, ich versuche es dennoch mal hier da ich mir unsicher bin, ob mein Ergebnis so stimmen kann.

Gegeben sei ein NFA M

(q0,q1,q2,q3),(a,b),delta, q0, (q0,q3)

Also

Startzustand: q0

Endzustände: q0 und q3

Übergangstabelle:

delta   q0                q1        q2        q3

a     (q1,q2)      (q1,q2)      (q2)     (q2) 

b         (q1)            (q1)      (q3)     (q1) 

Code:

Nun habe ich mithilfe des Potenzmengengesetzes einen DFA mit 16 Zuständen konstruiert: leere Menge, q0-q3, q01-q03, q12,q13,q23, q012, q023, q013, q123, q0123

Dort, wo ehemalige Endzustände vorkommen, wird der neue Zustand ebenfalls zum Endzustand. Dieser DFA ist sehr unübersichtlich und muss minimiert werden.

Normalerweise müsste jetzt eine Zustandspaartabelle erstellt werden und mithilfe des Minimierungsalgorithmus (keine Überprüfung mit sich selbst und Betrachtung nur in eine Richtung; Zustand a=Endzustand, Zustand b=kein Endzustand- wird gestrichen; übrige Zustände werden nach a und b nach bereits gestrichenen Zuständen überprüft und sollte dies der Fall sein auch gestrichen) Zustände verschmolzen werden.

Hier ist jedoch ein Großteil der Zustände nicht mit dem Startzustand verbunden, sodass nur durch betrachten gestrichen werden kann:

DFA M'

                a           b

q0          (q12)     (q1)

q1          (q12)     (q1)

q12        (q12)     (q13)

q13        (q12)     (q1)

Zustandsmenge q: (q0,q1,q12,q13)

Eingabealphabet Sigma: (a,b)

Startzustand: qstart= q0

Endzustände qende= q0, q13

Kann das so stimmen?

Comments

Ich versuche gerade den regulären Ausdruck zu berechnen, weil ich ihn so nicht sehen kann.

Zum einen geht das mit dem ardenschen Lemma oder mit der Formel R^k_{i,j}. Das ist die Annäherung an die Menge der Wörter, die den den Automaten vom Zustand i in den Zustand j übergehen lassen; das k ist ein Index. Ich fange mal mit der Formel an (erstelle Zustandspaartabellen für k von 0 bis 3) und nehme mir danach das Lemma vor. Wenn ich morgen soweit bin, poste ich das mal hier. Vielleicht erbarmt sich jemand mal drüberzuschauen:)

Answer 1

Du musst dich schon bei der Umwandlung vom NFA zu DFA und dementsprechend dann auch bei der Minimierung vertan haben. Hier meine Lösungen zum Vergleichen:

Ausgangsautomat

NFA -> DFA:

Minimierung:

Falls du Fragen zu den einzelnen Schritten hast, dann schreibe mir ein Kommentar!

Edit: Beim minimierten Automaten sollte sich mit den \(R_{ij}^k\) ein regulärer Ausdruck finden lassen. Wähle die Zustände dafür so, dass du mit dem höchsten Zustand die meisten Kreise zerstörst. Dann hast du weniger Schritte beim \(R_{ij}^k\)-Algorithmus zu machen.

Comments

Vielen Dank für die Antwort. Ich poste heute abend mal meine Tabelle der Potenzmengenkonstruktion, konnte nämlich beim drüberschauen selbst keinen Fehler finden.

Wegen der Minimierung habe ich mir mit Zustandselimination geholfen, möchte aber sowohl das ardensche Lemma als auch die Formel nutzen können. Ich setze mich also nochmal dran:)

---

Ich meinte natürlich nicht minimieren, sondern regulärer Ausdruck der die Sprache angibt. Ich poste aber heute noch wenn möglich meine Tabelle. Bin momentan sehr mit boolescher Algebra beschäftigt:)