André Vratislavsky

Übungsgruppe vom 08.02.2000

(Zu diesen Themen siehe auch Ingo Wegener, Kompendium Informatik)

Kontextfreie Sprachen/Grammatiken

Kontextfreie Sprachen sind ein mächtigeres Konzept als das der regulären Sprachen, so daß mit Ihnen auch Wörter dargestellt werden können, die nicht in regulären Sprachen enthalten sind. Z.B. ist {anbn| n nat. Zahl} kontextfrei aber nicht regulär. Man kann das so formulieren: "Ein endlicher Automat ist nicht in der Lage die Anzahl n der a's sich zu "merken", um sie mit der Anzahl der b's zu vergleichen."
Kontextfreie Sprachen sind ein wichtiges Konzept zur Darstellung von Programmiersprachen. Sie erlauben eine effiziente Lösung des Wortproblems. Zur Darstellung von Kontextfreien Programmiersprachen ist die Bachus-Naur-Form bekannt.
Der Begriff "kontextfrei" geht auf die Produktionsregeln zurück, in denen das Ergebnis nicht vom Kontext der Ausgangsterme abhängt. Das heißt, die linke Seite der Ableitungsregeln darf nur aus einer Variablen bestehen, also keinen Kontext aufweisen.
Es sind also nur Regeln von der Form A->w mit A ein Nichtterminalsymbole und w ein Wort aus Terminal- oder Nichtterminalsymbolen erlaubt.

Beispiel:

Gegeben: L={anbn|n nat.Zahl}
Behauptung: L= L(G) mit G=(V,T,P,S), wobei V={A}, T={a,b}, P={A->asb, A->epsilon}, S=A.
Beweis:
Es sind zwei Richtungen zu zeigen!
I) Sei w aus L. Dann läßt sich w=anbn wie folgt mit Regeln aus G erzeugen:
Die Ableitung A =G> aAb =G> aaAbb =G> ... =G> anAbn  =G> an(epsilon)bn=anbn verwendet nur Regeln aus G.
II) Sei w aus L(G). Alle Ableitungen aus G führen zum Ergebnis anbn aus L:
A =G> aAb =G> aaAbb =G> ... =G> anAbn  =G> an(epsilon)bn=anbn .

Syntaxbäume

Faßt man die Startvariable S als Wurzel auf, so läßt sich eine Ableitung eines aus Produktionen einer kontextfreien Grammatik gebildeten Wortes als Syntaxbaum darstellen. Die Variable vor dem Pfeil ist jeweils der Vater, die Symbole hinter dem Pfeil sind die Söhne. An den Blättern kann das gebildete Wort abgelesen werden. Für jedes Wort gibt es einen Baum. Es kann aber unter Umständen auch mehrere geben.
Es gibt keine Verbindungen zwischen den Teilbäumen, da es bei den Produktionen nicht auf die Kombination der Väter ankommt (Kontextfreiheit).
Wenn für jedes Wort einer kontextfreien Grammatik nur ein Syntaxbaum möglich ist, heißt die Grammatik "eindeutig", sonst "mehrdeutig".
Im allgemeinen sind wiederum für jeden Syntaxbaum mehrere Ableitungen möglich. Ersetzt man stets die linkeste Variable, so spricht man von der "Linksableitung".
Die Tatsache, daß man bei kontextfreien Grammatiken nur Syntaxbäume und nicht etwa beliebige Graphen untersuchen muß, läßt die effiziente Lösbarkeit des Syntaxanalyseproblems vermuten, also des Problems, zu entscheiden, ob ein Wort mit einer bestimmten Grammatik gebildet werden kann.
Bei regulären Grammatiken kommt man sogar mit Syntaxlisten aus.

Überführung einer kontextfreien Grammatik in Chomsky-Normalform (CNF)

Alle Regeln einer CNF haben die Form A->BC oder A->a, wobei A,B,C Variablen, a Terminalzeichen.
Jede kontextfreie Grammatik, die nicht das leere Wort erzeugt, kann in CNF überführt werden.

Vorgehensweise:

  • 1. Ziel: Auf rechter Seite nur Variablen oder nur ein Terminalsymbol.

    • - Ersetze Terminalsymbol a durch Ya.
    - Regel Ya->a einfügen.
  • 2. Ziel: Alle rechten Seiten haben Länge kleinergleich 2.

    • - Beispiel: A->B1B2B3B4 ersetzen durch
                         A->B1C1, C1->B2C2, C2->B3B4
                         Dabei werden die neuen Variablen C1, C2 benutzt.
  • 3. Ziel: Keine Regeln A->epsilon.

    • - Streiche Regeln A->epsilon.
    - Füge zusätzlich Kettenregel A->B ein für A->BC mit C=*>epsilon (bzw. für A->CB)
  • 4. Ziel: Chomsky-Normalform.

    • -    Kettenregel A->B streichen.
    -    Dafür für alle Regeln B->r Regel A->r hinzufügen.

    Younger-Algorithmus

    Mit dem Younger-Algorithmus kann das Wortproblem einer kontextfreien Sprache in Chomsky-Normalform mit dynamischer Programmierung gelöst werden.
    (Bottom-up-Methode: Alle Teilprobleme werden nach wachsender Problemgröße gelöst und die Lösungen in einer Tabelle gespeichert.)
    Ein Teilproblem Vij bei der Syntaxanalyse von w = w1...wn ist die Frage, aus welchen Variablen sich das Teilwort wi...wj ableiten läßt.
    Für alle i,j<=n werden die Teilprobleme Vij untersucht und die Lösungen in einer Tabelle notiert: Das eigentliche Problem ist V1,n. Das Wort w ist genau dann ableitbar, wenn das Startsymbol S in V1,n ganz oben in der Tabelle eingetragen ist.

    Abschlußeigenschaften kontextfreier Sprachen

    Kontextfreie Sprachen sind abgeschlossen gegenüber Vereinigung, Konkatenation, *-Bildung und Durchschnitt mit regulärer Menge
    Kontextfreie Sprachen sind NICHT abgeschlossen gegenüber Durchschnitt, Komplement .

    Das Pumping-Lemma für kontextfreie Sprachen

    Das Pumping-Lemma für reguläre Sprachen ist eine notwendige, aber nicht hinreichende Eigenschaft regulärer Sprachen.

    L regulär =>
    Es ex. eine nat. Zahl N (z.B. Zustandszahl)
        So daß für alle Worte w aus L mit |w|>=N
            Eine Zerlegung w=uvx ex. mit |uv|<=N (Anfangsstück) und |v|>=1 (Pumpstelle)
                So daß für alle i>=0 gilt: uvix ist aus L.

    Die Kontraposition dieses Satzes dient zum Nachweis der Nichtregularität:

    Für alle Nat. Zahlen N
        Gibt es ein Wort w aus L mit |w|>=N
            So daß für alle Zerlegungen w=uvx mit |uv|<=N und |v|>=1
                Ein i>=0 ex., so daß gilt: uvix ist nicht aus L.
    => L ist nicht regulär.

    Das Pumping-Lemma für kontextfreie Sprachen ist eine notwendige, aber nicht hinreichende Eigenschaft kontextfreier Sprachen.

    L kontextfrei =>
    Es ex. eine nat. Zahl N
        So daß für alle Worte z aus L mit |z|>=N
            Eine Zerlegung z=uvwxy ex. mit |vwx|<=N (Mittelstück) und |vx|>=1 (Pumpstelle)
                So daß für alle i>=0 gilt: uviwxiy ist aus L.

    Die Kontraposition dieses Satzes dient zum Nachweis der Nichtkontextfreiheit:

    Für alle Nat. Zahlen N
        Gibt es ein Wort z aus L mit |z|>=N
            So daß für alle Zerlegungen z=uvwxy mit |vwx|<=N und |vx|>=1
                Ein i>=0 ex., so daß gilt: uviwxiy ist nicht aus L.
    => L ist nicht kontextfrei.

    WICHTIG:
    Der umgekehrte Schluß (<=) gilt nicht!
    D.h., Kontextfreiheit ist nicht durch das Pumping-Lemma beweisbar!

    Beispiel

    L={0n1n2n|n nat.Zahl}

    Sei N nat. Zahl
        Wähle Wort z=0N1N2N, |z|=3N>=N
            Sei Z=uvwxy bel. Zerlegung mit |vwx|<=N, |vx|>=1
                Wähle i=2:
                1.Fall:
                v oder x enthalten zwei Buchstabentypen
                => in uv2wx2y wird Reihenfolge 0-1-2 nicht eingehalten
                2.Fall:
                v und x enthalten jeweils nur einen Buchstabentyp
                => ein oder zwei Buchstabentypen werden gepumpt und einer nicht
                => uv2wx2y ist nicht vom Typ 0n1n2n
    => L ist nicht kontextfrei.