Suche Home Einstellungen Anmelden Hilfe  

4.3.2 Reguläre Ausdrücke und Dycksprachen

Reguläre Ausdrücke RA: RA lassen sich mit nur wenigen Basiskomponenten bilden. Die leere Menge, das leere Wort und jedes Zeichen aus dem Alpabet sind RA. Aus bestehenden RA lassen sich neue mittels Sternbildung, Verknüpfung (Konkatenation) und Vereinigung bilden.

RAL(G)
ØØ
ε{ε}
a (für alle a in T){a}
 Sind r1 und r2 RA, dann auch
RAOperation
r1 | r2Vereinigung
r1r2Konkatenation
r1*Sternbildung
Beispiele: {a*b*}*a, {a|b}*aba{a|b}*

Reguläre Ausdrücke sind ein Beschreibungsmittel für reguläre Sprachen. Sie stehen damit auf einer Stufe mit einseitig linearen Grammatiken und Endlichen Automaten.


 
Schema für die Verarbeitung von Dycksprachen. Der Keller eines KA kann die Zeichen so speichern, dass sie korrekt ineinander geschachtelt sind.
Verarbeitung einer kontextfreien Sprache mit einem Kellerautomaten.

Dycksprachen Dn: Dycksprachen sind Klammersprachen. In den Wörtern einer Dycksprache wird jede öffnende Klammer auch wieder geschlossen. Außerdem sind die Klammerpaare ineinander verschachtelt, d.h. es gibt keine Überkreuzungen. Der Index n IN bezeichnet die Anzahl der unterschiedlichen Klammerpaare.

Beispiele:
DnWörter aus Dn
D1()()(), ()((()())()), (()())
D2[()[()]], []()[](), ([()])[(()[])]
D4[{}{}](), (<<><>>)()({[]([])}{})

Die Dycksprachen sind kontextfrei. Man kann das leicht nachvollziehen, indem man sich die Verarbeitung einer Dycksprache mit einem Kellerautomaten vorstellt: Jede öffnende Klammer wird im Keller abgelegt. Wird eine schließende Klammer eingelesen, so wird verglichen, ob sie zu der öffnenden Klammer im Keller passt. Diese Vorgehensweise verdeutlicht auch die Notwendigkeit von Schachtelungen.

Arbeiten Sie mit dem JFLAP-Tool an einem Beispiel zur Schnittmengenbildung.

Abgeschlossenheit gegenüber Schnittmengenbildung: Die Abgeschlossenheit von kontextfreien Sprachen gegenüber der Schnittmengenbildung mit regulären Sprachen lässt sich am besten durch einen Automaten verdeutlichen.

    Sei M = (QM, Σ, ΓM, δM, q0, Z0, FM) ein Kellerautomat
    und
    A = (QA, Σ, δA, p0, FM) ein Endlicher Automat,
     
    dann ergibt sich M' mit L(M') = L(M) ∩ L(A):
     
    M' = (QA x QM, Σ, ΓM, δ, [p0,q0], Z0, FA x FM) mit ([p',q'],Y) δ([p,q],a,X)
    für (q',Y) δM(q,a,X) und (p' δA(p,a) oder (a=ε und p' = p, bei ε-Übergängen des KA))

Bei der Verarbeitung eines Eingabewortes werden beide Automaten parallel abgelaufen. Befinden sich am Wortende beide Automaten in einem Endzustand, so wird das Wort akzeptiert.

Prinzip 1   2   3   4   5   6 Homomorphismen

Benutzer: Gast • Besitzer: senn • Zuletzt geändert am: