regulärer Ausdruck umwandeln |
| 07.11.2007, 13:12 | Auf diesen Beitrag antworten » |
| Phoney | 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, 14:04 | Auf diesen Beitrag antworten » |
| Tobias | (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:26 | Auf diesen Beitrag antworten » |
| Phoney | 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, 20:34 | Auf diesen Beitrag antworten » |
| Tobias | 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. |
| Anzeige | |
|
|
|
|
|
