# NFA in DFA, NFAepsilon, DFA Minimierung



## b1zarRe (28. Jul 2011)

Hi (ich wieder... ),

Noch einige Fragen zu Automaten:

*1.) NFA in DFA*
Ich habe mir folgenden NFA gebastelt und verstehe leider nicht, wie ich mit einer gewissen Methodik - und nicht durch probieren, daraus einen DFA basteln kann. Hier als Bild der NFA sowie die
Übergangstabelle: http://www7.pic-upload.de/28.07.11/yu6zfvuhya7.jpg


*2.) NFAepsilon*
Hier ein aufgemalter NFAepsilon zu dem Regulären Ausdruck: [abc*] [a + b]* :
http://www7.pic-upload.de/28.07.11/z998kwlmfrgl.jpg

Sieht der erstmal richtig aus??? Wie leite ich davon genau einen "normalen" Automaten(sprich: Epsilonlosen Automaten) auf? E-Übergänge streichen und einfach verbinden geschieht bei mir
leider auch leicht durch raten bzw. probieren. Zum Beispiel würde ich an der Stelle c* einfach
über b eine Verbindung zu einem Zustand machen wo mit n vielen C's der in den gleichen Zustand geht. Ist das korrekt? Oder gibt es da auch eine Methodik?

*3.) DFA Minimierung*
Hier der Automat: http://www7.pic-upload.de/28.07.11/u5abhw9lt3l9.jpg
1. Ich habe geguckt ob der Automat total ist. Ist er nicht, also noch einen "Todzustand" hinzugefügt
2. Übergangstabelle Siehe Bild
3. Minimierungstabelle Siehe Bild
4. Minimierungstabelle: Alle Zustände sind zu sich selbst äquivalent(da reflexiv). Die obere Tabellenform wird nicht gebraucht also als nicht äquivalent markiert ("x"). Nun habe ich nacheinander alle übringen Paare betrachten, sprich: S0-S1, S0-2, S1-S2

Soviel ich weiß, markiert man diese mit NICHT äquivalent, wenn:
1. Aus einem NICHT Endzustand etwas in einen Endzustand übergeht(oder andersherum).
2. Und nur mit Äquivalent, wenn ein Zustand a in b übergeht, dieser widerum in a übergeht und mit der anderen Zahl beide Zustände das gleiche machen... <- *Ist dies korrekt?!*

Hiernach könnte man diesen Automaten nicht weiter minimieren?

Vielen Dank euch, echt prima hier wie schnell geholfen wird 

EDIT:
Zur Sicherheit: MUSS ein DFA *immer* total sein? Kann ein NFA bzw. DFA bzw Epsilon Automat beliebig viele Endzustände haben? -> Ich gehe im moment von nein (erste Frage) bzw. ja(zweite Frage) aus.


----------



## aze (29. Jul 2011)

zu 1) Man kann einen NFA in einen DFA mithilfe der Potenzmengenkonstuktion umwandeln:

Potenzmengenkonstruktion ? Wikipedia


----------



## b1zarRe (30. Jul 2011)

YEAHR.. endlich gecheckt!

Ist dies korrekt? http://www7.pic-upload.de/30.07.11/zuf3rdg9jdd.png (Zu NFA in DFA)


----------

