---

Geschrieben von Phoney am 07.11.2007 um 13:12:

  regulärer Ausdruck umwandeln

Hallo
Hier ist ein regülärer Ausdruck gegeben ((a* vereinigt b*)ab)*

Also erst einmal ist mir die Bedeutung nicht klar
a* bedeutet ja so viel wie: es können beliebig viele a kommen, 0,1,2,3,4...
b* das gleiche
(ab)* würde z.b. bedeuten ababababab.

Was genau bedeutet jetzt die Vereinigung?

Jetzt habe ich die Aufgabe, aus diesem Ausdruck einen DEA zu erstellen. Wie geht man da am geschicktesten vor?

Grüße von Phoney

---

Geschrieben von Tobias am 07.11.2007 um 14:04:

 

(a* vereinigt b*) oder oft auch (a* + b*) sind alle Wörter, die entweder aus a* oder aus b* gebildet werden können.

Also z.B.

aaaaaa ist in L(a* + b*)
bbbbbbbb ist in L(a* + b*)

aber NICHT: abaaabab ist in L(a* + b*)

Die allgemeine Vorgehensweise ist, sich mit der Thompson-Konstruktion einen NEA zu bauen (mit Epsilon-Übergängen) und dann mittels Potenzmengenkonstruktion einen DEA zu erhalten.

---

Geschrieben von Phoney am 07.11.2007 um 14:26:

 

Was heißt denn mit e-Übergängen gibts die auch ohne bei der Thompson-Konstruktion?

Wenn ich umgekehrt einen DEA habe, wie wandel ich es dann in einen regulären Ausdruck um?
Muss doch eigentlich nur von DEA zum Thompson-Automaten. Gibts da auch ein Schlagwort?

Danke

---

Geschrieben von Tobias am 07.11.2007 um 20:34:

 

Ich wollte ausdrücken, dass die Thompson-Konstruktion nicht ohne Epsilon-Kanten auskommt und du deswegen keinen DEA sondern einen NEA bekommst, den du dann noch zusätzlich in einen DEA umformen musst.

Die Rückrichtung DEA -> RegExp funktioniert mit Zustandselimination.