 regulärer Ausdruck umwandeln |
Phoney
Jungspund
Dabei seit: 13.12.2006
Beiträge: 20
 |
|
| 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
|
|
07.11.2007 13:12 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
(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.
|
|
|
07.11.2007 14:04 |
|
|
Phoney
Jungspund
Dabei seit: 13.12.2006
Beiträge: 20
|
|
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
|
|
|
07.11.2007 14:26 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
|
07.11.2007 20:34 |
|
|
|
