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.
),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.
Zuletzt bearbeitet:
