2.3.1 Syntaxdiagramme von regulären Ausdrücken
Im letzten Abschnitt haben wir den Syntax (also die Form) von regulären Ausdrücken kennengelernt. Diese lässt sich auch grafisch darstellen. Die Syntaxdiagramme von regulären Ausdrücken ist das Thema dieses Abschnitts.
Starten wir mit denselben Beispielen des letzten Abschnitts.
Beispiele
- \(a(b(ba)) \)
- \((ab)|(baa)\)
- \(((ab)|(baa))bb\)
- \((aa)^*b\)
- \(((ba)|b)^*\)
- \((bb)^*a^*b(ba)\)
Folgende Muster können wir erkennen.
- Alle Syntaxdiagramme beginnen mitund enden mit.
- Für eine Kleensche Hülle (beliebige Wiederholung) \(a^*\) zeichnen wir eine Schleife . Diese kann beliebig oft durchlaufen werden.
- Für eine Konkatenation \(ab\) hängen wir die Pfeile aneinander.
- Für eine Alternative \(a|b\) zeichnen wir eine Verzweigung, welche wieder zusammengeführt wird.
Eine naheliegende Aufgabe ist, aus einem Syntaxdiagram einen passenden regulären Ausdruck herauszulesen.
Übung
Geben Sie zu den folgenden Syntaxdiagrammen einen passenden RA an.
Hinweis: RA sind nicht eindeutig. Ihre Lösung kann also auch korrekt sein, wenn Sie von der Musterlösung abweicht.
Äquivalenz von regulären Ausdrücken und endlichen Automaten
Die Syntaxdiagramme von regulären Ausdrücken haben eine auffallende Ähnlichkeit zu den grafischen Darstellungen von endlichen Automaten. Tatsächlich erhalten wir aus den Syntaxdiagrammen sehr schnell endliche Automaten, indem wir die Pfeile mit den Eingaben beschriften, die Zwischenstopps mit Zuständen \( q_0, q_1, …\) etc. anschreiben, die letzten Zustände doppelt einkreisen und den Startzustand mit dem Eingangspfeil markieren. Spontane ε-Übergänge sind hilfreich und können nach Wunsch in einem späterem Schritt eliminiert werden.
Umgekehrt gibt es auch zu jedem endlichen Automaten einen passenden regulären Ausdruck, welcher genau die Wörter beschreibt, für welche der endliche Automat in einem akzeptierenden Zustand landet. Dies ist jedoch etwas schwieriger einzusehen.
Beispiele
- Mit \(a(b(ba)) \) beziehungsweise erhalten wir den EA .
- Mit \((ab)|(baa)\) beziehungsweise erhalten wir den EA .
Es ist auch möglich, direkt aus einem RA einen ε-NEA zu zeichnen. Hier finden Sie heraus, wie Sie dies tun können.
Von RA zu ε-NEA:
Wir zerlegenden den RA anhand der folgenden Regeln in kleinere RA, bis die kleinsten RA nur noch aus einzelnen \(a \in ∑\) bestehen.
- Für eine Kleensche Hülle (beliebige Wiederholung) \(R^*\) zeichnen den RA \(R\) mit folgenden ε-Übergängen.
- Für eine Konkatenation \(RS\) hängen wir die einzelnen RA \(R\) und \(S\) mittels ε-Übergang hintereinander.
- Für eine Alternative \(R\vert S\) zeichnen wir mit Hilfe von ε-Übergängen eine Verzweigung zu den einzelnen RA \(R\) und \(S\), welche wieder mittels ε-Übergänge zusammengeführt werden.
Hier haben Sie die Option Notizen, Screenshots und Bilder zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung wie z. B. 2_3_1_regEx_syntaxDiagr_Notizen.