0 Daumen
1,3k Aufrufe

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?

Avatar von

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:)

1 Antwort

0 Daumen

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.png

NFA -> DFA:

dea.png

Minimierung:

mindea.png

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.

Avatar von

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:)

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten
+1 Daumen
0 Antworten
0 Daumen
1 Antwort

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community