Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Regulärer ausdruck für nicht-aba (Klausur I-1 Herbst 04)
Dabei gehts darum einen regulären Ausdruck für eine Sprache anzugeben, die nicht aba enthält.
Leider komme ich nur auf Lösungen die nicht alle anderen Sprachen abdecken…
wie z.B.
[b*a*bb]*
trifft leider nicht bei
abbabbba
zu.
Hab mich mal dran versucht, hab zu viel Zeit und ist bestimmt auch falsch:
b*(abbba*)|a)b
Idee: zwischen as dürfen nur zwei oder kein b stehen. Dann noch die b* außenrum für einzelne bs am Anfang oder Ende.
Edit2: komplett überarbeitet :-).
b | ( ba | (a | bb )* . (b | ε))
Danke!
Was bedeutet der . bei dir? Ich kenn den Punkt nur als ein beliebiges Zeichen.
Würde das Wort „baa“ dann auch von deinem Ausdruck erkannt werden?
b * ( abb b* | a)*
:rolleyes: :rolleyes: :rolleyes: :rolleyes: :rolleyes:
könnte auch gehen, oder?
was passiert da mit „ab“?
Ich hab mal einen Automaten mit Hilfe vom Arden Lemma auf einen regulären Ausdruck gebracht. Besteht da Interessse, dass ich den Lösungsweg mal poste?
ja!!!
des soll ne konkatenation sein
edit:
( ba | (a | bb )* (b | ε) ← reicht sogar
Das wort baa wird aber von deinem Ausdruck immer noch nicht erkannt. So wie du es schreibst, kann das Wort aus „ba“ oder beliebig oft wiederholt aus „a“ oder „bb“ und evtl. ein „b“ am Ende bestehen. „baa“ wird damit aber nicht abgedeckt. Bei dir gehen aber 3 Klammern auf aber nur 2 wieder zu. Hast du da evtl was vergessen?
ja die erste klammer is unnütz. stimmt.
du scheinst recht zu haben
(b | ε) (a | bb )* (b | ε)
dann sag ich mal so 
abbba geht nicht.
Neuer Vorschlag:
b*(bbb*|a*)b
okay. dann vergesst meinen ansatz
Regulärer Ausdruck mit Arden
Also das Arden Lemma besagt folgendes:
Wenn man eine Gleichung in der Form:
L = AL + B hat, dann ist L = A*B eine Lösung dieser Gleichung.
Aber vorsicht, das “+” ist keine Addition im herkömmlichen Sinne sondern ein ODER. “a + a” wäre also nicht 2a oder a² oder sowas in der Richtung sondern einfach nur wieder “a”. Deswegen schreibe ich die Gleichungen mit “∪”, dann wird es einsichtiger, was gemeint ist.
Aufgabe II-1 a) sollte klar sein. (Bild vom Automat ist im Anhang)
Den Automaten, der “aba” nicht erkennt, ist einfach der inverse Automat zu a)
Es werden also alle nicht-Endzustände zu Endzuständen und alte Endzustände werden zu Fehlerzuständen (hab ich im Bild aber weggelassen).
Es wird nun dieser Automat analysiert:
Vom Startzustand z0 aus bleibe ich mit einem “b” im Startzustand. Mit einem “a” komme ich in Zustand z1. Da der Zustand ein Endzustand ist, wird auch das leere Wort akzeptiert. Man bekommt also folgende Gleichung:
[m]
(1) L0 = bL0 ∪ aL1 ∪ ε (ε = leeres Wort)[/m]
Von z1 aus bleibt man mit einem “a” im z1 und mit einem “b” kommt man in z2. Außerdem ist der Zustand akzeptierend.
m L1 = aL1 ∪ bL2 ∪ ε[/m]
Von z2 aus kommt man nur mit einem “b” in den z0. Außerdem wieder ein Endzustand
[m]
(3) L2 = bL0 ∪ ε[/m]
Anmerkung: Wäre irgendeine Zustand kein Endzustand, dann käme in der Gleichung auch kein ε vor.
Setzen wir nun L2 in L1 ein:
[m]
(2’) L1 = aL1 ∪ b(bL0 ∪ ε) ∪ ε = aL1 ∪ bbL0 ∪ b ∪ ε[/m]
(Man beachte das "Ausmultiplizieren der Klammer)
Mit Hilfe des Arden Lemmas kann man das außerdem noch umformen:
[m]
(2’') = L1 = (a)(bbL0 ∪ b ∪ ε) = abbL0 ∪ ab * ∪ a [/m]
auch hier wieder die Klammern beachten
Die Gleichung (2’') wird nun in (1) eingesetzt
m L0 = bL0 ∪ a(abbL0 ∪ ab * ∪ a*) ∪ ε = bL0 ∪ aabbL0 ∪ aab ∪ aa* ∪ ε[/m]
Nun Klammern wir das L0 aus:
[m]
(1’') L0 = (b ∪ aabb)L0 ∪ aab ∪ aa* ∪ ε[/m]
darauf lassen wir wieder das Arden Lemma los:
[m]
L0 = (b ∪ aabb)( aab ∪ aa ∪ ε)[/m]
Also ist das unser gesuchter regulärer Ausdruck: (b | aabb)( aab | aa | ε)
Wie man leicht sieht, ist das nicht die einzige Lösung (und auch nicht die kürzeste) aber eben eine Methode, wie man sicher zu einem korrekten Ausdruck kommt.
Zum Überprüfen von Ausdrücken kann ich dem Kregexpeditor von KDE empfehlen. Damit kann man schnell mal seine gefundenen Ausdrücke testen.
Attachment:
ii-1-sep04.jpg: https://fsi.cs.fau.de/unb-attachments/post_19132/ii-1-sep04.jpg
sag mal: Gleichungen stelle ich doch nur fuer den Startzustand und die Endzustaende auf, oder sehe ich das verkehrt? ich war mir eben net sicher, deshalb die peinliche frage…
Nö, die stellst du für alle Zustände auf, nur kommt bei nicht-Startzuständen kein leeres Wort mit in die Gleichung.
Wenn du es nicht tun würdest und aus dem Startzustand nur ein Übergang in einen nicht-Endzustand möglich wäre, dann könntest du die Gleichung nicht lösen, wenn du die Gl. für den 2. Zustand weglässt.
Fehlerzustände muss man weglassen, weil damit kein Wort der Sprache erzeugt wird. Zustände aus denen man nicht mehr herauskommt und kein Endzustand sind, müssten auch vernachlässigbar sein (ist ja im Grund wie ein Fehlerzustand)
ja, ok, ich glaub sowas hatte ich gemeint, irgendwie hab ich das net ganz richtig formuliert. wunderbar, danke!