---

Geschrieben von cirruswolke am 14.07.2007 um 13:19:

  NFA in DFA umwandeln

Hallo ich habe folgende reguläre Grammatik gegeben:
G=({A,B,S}, {a,b},P,S) mit
P={S-> aB|bA
A-> a| aS
B-> b | bS}

Daraus habe ich einen NFA gebaut wie im Anhang zusehen und dann habe ich vrsucht einen DFA zubauen: Wo liegen meine Fehler?????

---

Geschrieben von kiste am 16.07.2007 um 19:31:

 

Dein NFA ist falsch. Er aktzeptiert das Wort baaa das ist aber nicht produzierbar:
S->bA->baS->baaB->... und spätestens hier kommt wieder ein b. Führe also noch einen Endzustand ein für die Produktionen der Form A -> a, alle anderen Zustände sind keine Endzustände