Formale Sprachen, Teil 3: Kontextfreie Sprachen

Das ist die Fortsetzung dieses Eintrags. Aber danach gibt es erst mal wieder Blogeinträge, die vielleicht von allgemeinerem Interesse sind, bevor ich mich dann an die richtig schwierigen Sachen wage.

Nehmen wir als Alphabet wieder nur {a, b}. Aus diesen zwei Zeichen kann man unendlich viele Wörter kombinieren. Greifen wir eine Teilmenge davon heraus, dann ist das eine Sprache. Die Sprache zum Beispiel, die aus allen Wörtern besteht, die genau so oft den einen wie den anderen Buchstaben enthalten, ist eine kontextfreie Sprache, vom Typ Chomsky 2. Sie kann durch eine kontextfreie Grammatik beschrieben werden; ihre Wörter werden von einem Kellerautomaten akzeptiert. (Mit der regulären Grammatik vom letzten Eintrag kann man diese Sprache nicht beschreiben.)

1. Kontextfreie Grammatik

1. S => aSB
2. S => bSA
3. S => ε (das heißt so viel wie nichts/null)
4. A => aS
5. B => bS

Diese Grammatik beschreibt die Sprache aller Wörter über {a, b}, in denen beide Buchstaben gleich oft vorkommen, einschließlich des leeren Worts.
Das Wort ababba kann man mit den Regeln so ableiten, fett gedruckt ist jeweils das Nichtterminal, das in der folgenden Zeile ersetzt wird:

Regel 1: S => aSB
Regel 5: => aSbS
Regel 2: => aSbbSA
Regel 3: => aSbbA
Regel 4: => aSbbaS
Regel 3: => aSbba
Regel 2: => abSAbba
Regel 4: => abSaSbba
Regel 3: => abSabba
Regel 3: => ababba

Und fertig. Gibt es eine kürzere Ableitung des Wortes? Gibt es eine kürzere Grammatik, die dieselbe Sprache beschreibt? Mir gefällt dieses ε nicht, da gehört das leere Wort ja auch zur Sprache; kann ich die Grammatik auch ohne das schreiben? Legitime Fragen, auf die es Antworten gibt.

Für eine kontextfreie Grammatik gelten folgende Einschränkungen:

  • Links vom Pfeil steht immer nur genau ein Nichtterminalzeichen. (Im Beispiel: Großbuchstaben.)
  • Rechts vom Pfeil dürfen Terminale und Nichtterminale in beliebiger Folge und Anzahl stehen. Außerdem darf es eventuell noch die Regel S => ε geben.

Gibt es überhaupt Sprachen, bei denen es wichtig ist, dass genau so oft das eine Zeichen auftaucht wie das andere? Aber ja. Stellen wir uns nur die Zeichen „(“ und „)“ oder „{“ „}“ oder „if“ und „endif“ vor – bei jedem Computerprogramm, bei jedem deutschen Satz, bei dem eine Klammer aufgemacht wird, muss auch wieder eine zugemacht werden. Wenn das brav nacheinander geschieht – Klammer auf, Klammer zu, Klammer auf, Klammer zu – dann geht das zur Not auch mit einer regulären Sprache. Aber sobald man verschachteln kann, sobald es Klammern in Klammern gibt, dann braucht man eine kontextfreie Grammatik. Und verschachteln kann man eben auch in natürlicher Sprache, wo eine Nominalphrase als Genitivattribut wieder eine Nominalphrase enthalten kann, die als Präpositionalattribut wieder eine Nominalphrase enthalten kann, und so weiter.

2. Kellerautomat

„Keller“ ist die deutsche Übersetzung des englischen „stack“. Man kann auch Stapel dazu sagen. Ein Stapel kann beliebig hoch werden (ein Keller beliebig tief), man kann immer noch etwas drauflegen. Abgebaut wird der Stapel in umgekehrter Reihenfolge. Man kann also nicht unmittelbar auf ein Element mitten im Stapel zugreifen, sondern muss erst das abarbeiten, was darüber liegt.
Den Kellerautomaten will ich hier nicht beschreiben. Es sei nur gesagt, dass er eben über einen Keller/Stapel/stack verfügt, der beliebig groß werden kann. Das ist der Hauptunterschied zum endlichen Automaten. Es gibt auch beim Kellerautomaten einen Startzustand und mindestens einen akzeptierenden Zustand, wohl auch mehrere nicht akzeptierende Zustände. Wenn das Wort abgearbeitet ist, bleibt der Automat in einem Zustand stehen. Immer. Bleibt er in einem akzeptierenden Zustand stehen, gehört das Wort zur Sprache, sonst nicht.

(„Stack“ kennt man auch vom „stack overflow“, einer typischen Sicherheitslücke beim Programmieren.)

3. Beispiele

1. Programmiersprachen

Alle Programmiersprachen können mit einer kontextfreien Grammatik beschrieben werden. Hier ist eine nicht ganz vollständige Grammatik in der übersichtlicheren Backus-Naur-Form, die die Programmiersprache von Robot Karol beschreibt. Die Grammatik lässt allerdings noch keine selbst definierten Anweisungen und Bedingungen zu, Absätze und Kommentare, die die Übersichtlichkeit erhöhen, habe ich ebenfalls weggelassen. Im Prinzip wären das aber jeweils nur wenige Zeilen mehr.

<Programm> :: = <Anweisung>
<Anweisung> ::= <vordefinierte Anweisung> |<Sequenz> | <Entscheidung> | <Wiederholung>
<vordefinierte Anweisung> ::= "linksDrehen" | "rechtsDrehen" | "Schritt" | "Hinlegen" | "Aufheben" | "MarkeSetzen" | "MarkeAufheben"
<Sequenz> :: = <Anweisung>*
<Entscheidung> ::= "wenn" <Bedingung> "dann" <Anweisung> "sonst" <Anweisung> "*wenn"
<Bedingung> ::= "istWand" | "nichtIstWand"| "istZiegel"| "nichtIstZiegel" |"istMarke" | "nichtIstMarke"
<Wiederholung> ::= <Wiederholung mit Bedingung> | <Wiederholung mit fester Anzahl>
<Wiederholung mit Bedingung> ::= "wiederhole solange" <Bedingung> <Anweisung> "*wiederhole"
<Wiederholung mit fester Anzahl> ::= "wiederhole" <Zahl> "mal" <Anweisung> "*wiederhole"
<Zahl> ::= <Zahl>+
<Zahl> ::= 1|2|3|4|5|6|7|8|9|0

Alles in spitzen Klammern ist ein Nichtterminal, <Programm> ist der Startpunkt, alles in Anführungszeichen ist ein Terminal. Wer sich an diese Grammatiken hält, erzeugt immer ein „Wort“ der Robot-Karol-Sprache – will heißen, immer ein syntaktisch korrektes Robot-Karol-Programme. Ob das Programm auch das tut, was man möchte, ist eine andere Frage, ebenso die, ob das Programm zur Laufzeit einen Fehler ergibt, also ob Robot Karol gegen eine Wand läuft.

2. Eine Grammatik, angelehnt an die natürliche Sprache

<Satz> ::= <Nominalphrase> <Verbalphrase>
<Nominalphrase> ::= <Determiner> <Nomen>
<Determiner> ::= der | das | die | dieser | dieses | diese | jener | jenes | jene
<Nomen> ::= Hund | Katze | Maus | Mann | Frau | Kind | Knochen
<Verbalphrase> ::= <VerbTransitiv> <Nominalphrase>
<VerbTransitiv> ::= fraß | küsste | suchte | fand | warf

Damit kann man solche „Wörter“ (wir nennen sie sonst: Sätze) ableiten:

                   Satz
                 /     \
               NP       VP   
              / \      /   \  
             D   N    V    NP
          Jene Katze fraß  / \
                          D   N
                         die Maus

Warum passt diese Art Grammatik eher zur englischen Sprache? Schon mal, weil „the“ sich weder durch Numerus, Kasus noch Genus ändert, anders als im Deutschen. Damit man also Sätze verhindert wie: „Der Katze fraß den Maus“, muss man die Regeln noch weit verfeinern. Mehr dazu – aus der sprachwissenschaftlichen, nicht der informatischen Seite – bei: generative Grammatik (Wikipedia).

3. Logische Ausdrücke

<wff> ::= p | q | r |s
<wff> ::= N<wff>
<wff> ::= K<wff><wff> | A<wff><wff> | E<wff><wff> | C<wff><wff>

Mit diesen Regeln kann man Ausdrücke erzeugen wie {p, q, r, s, Np, Nq, Nr, Ns, Kpp, Kpq, NKpq, KpANpEqq … } – und diese Ausdrücke bedeuten etwas (ich sag nur WFF ‚N PROOF).

4. Das Wortproblem für kontextfreie Sprachen

Das Wortproblem wird später noch einmal wichtig. Es lautet: Kann man einen Algorithmus bauen (also zum Beispiel einen solchen Automaten), der für jedes beliebige Wort zu einem gegebenen Alphabet in endlicher Zeit entscheidet, ob das Wort zu einer bestimmten Sprache gehört oder ob es nicht dazu gehört? Ja, man kann. Für kontextfreie Sprachen ist das Wortproblem entscheidbar. Nach endlicher Zeit bleibt der Kellerautomat stehen, und zwar entweder in einem akzeptierenden Zustand oder nicht.

5. Zusammenfassung

Kontextfreie Sprachen sind wichtig für die Entwicklung und Umsetzung von Programmiersprachen. Auch natürliche Sprachen können – falls überhaupt – mit einer kontexfreien Grammatik beschrieben werden. (Nachtrag. Stimmt so nicht, siehe Kommentar unten.) Aber nicht alle Sprachen kann man mit einer kontextfreien Grammatik erzeugen. Das Standardbeispiele ist aibici, also die Sprache aller Wörter, die aus einer Reihe von a’s bestehen, gefolgt von ebenso vielen b’s, gefolgt von ebenso vielen c’s.

Teil 4 folgt nach einer kleinen Pause.

14 Antworten auf „Formale Sprachen, Teil 3: Kontextfreie Sprachen“

  1. „Auch natürliche Sprachen können – falls überhaupt – mit einer kontexfreien Grammatik beschrieben werden.“ Damit kommt man nicht hin. In der Computerlinguistik arbeitet man heute vielfach mit Klassen formaler Sprachen, die etwas mehr als kontextfrei sind – aber natürlich nicht gleich kontextsensitiv, dafür könnte man keine effizienten Parser bauen. Eine wichtige Klasse ist die der „Mildy context-sensitive languages“ (http://en.wikipedia.org/wiki/Mildly_context-sensitive_language), die z.B. die aibici-Sprache enthalten, auch noch die aibicidi-Sprache, aber nicht mehr aibicidiei (man denke sich die i’s hochgestellt). Eine andere wichtige MCSL ist die „copy language“, die alle Zeichenfolgen enthält, die aus zweimal derselben Zeichenfolge bestehen.

    Die klassische linguistische Motivation dafür, eine gewisse Kontextsensitivität zu erlauben, liefern Sprachen wie das Schwyzerdütsche oder Holländische mit ihren „cross-serial dependencies“, wo bestimmte Verben im Verbalkomplex in derselben Reihenfolge stehen wie ihre Argumente – und nicht etwa in der umgekehrten, wie man sich das beim Bauen einer kontextfreien Grammatik wünschen würde. Ein holländisches Beispiel (von http://www.let.rug.nl/~vannoord/papers/acl94/node5.html):

    dat An Bea Cor wil zien kussen
    wörtlich: dass An Bea Cor will sehen küssen
    bedeutet: dass An Bea Cor küssen sehen will

  2. Nederlands is en blijft een grappig taal! Ich versuch mich seit 2 Jahren daran – ansich recht erfolgreich aber diese Konstruktion laesst mich immernoch stutzen.

  3. Wow. Danke, das finde ich spannend. Uhm, für einen der nächsten beiden Einträge, irgendwann mal, bräuchte ich eine kontextsensitive Grammatik für eine solche copy language, also L = {w1w2 | w1=w2}, gerne wieder nur über {a,b}. Das war eine Standardaufgabe, die Lösung ist sicher irgendwo in meinen Unterlagen, aber ich komme selber nicht mehr drauf. Ich brauche das als Teil einer Aufgabe, die ich mir selber gestellt habe habe.
    Kann mir da jemand helfen?

  4. Letzter Nachtrag: In meinen Schatzkästlein bin ich auf Queries ’n Theories gestoßen, ein Spiel aus dem Hause Wff’n Proof. Ob es wirklich spielbar ist, weiß ich nicht. Die Anleitung ist jedenfalls genauso abschreckend.

    Das Spielprinzip: Es gibt Chips in verschiedenen Farben, ein Spieler legt daraus einige Startwörter und Ableitungsregeln, die anderen müssen auf die Regeln kommen.

    „Players try to detect the properties of a generative language that one of the players (the Native) has secretly defined by building a set of Basic Sentences and Replacement Rules.“ Die Methode: Die Spieler können mit ihren Farbchips Vermutungen formulieren, die der Spielgeber beantworten muss. Das sehr abstrakte Spiel kann interpretiert werden einerseits als Grammatik-Spiel, komplett mit kleinen Syntaxbäumen im Anhang, andererseits als Übung im induktiven Denken/der Formulierung von Thesen, ähnlich wie Eleusis.

  5. Dankeschön für diese Blogposts über formale Sprachen.

    Sehr, sehr toll! Bin selbst Informatikstudent und finde deine Artikel wirklich klasse! Werde dein Blog weiterempfehlen.

    Mach weiter so!

    LG Andreas

  6. Ich mache eine Seminararbeit über die Chomsky Hierarchie und hätte es ohne deine Blogeinträge deutlich schwerer!

    Nun bin ich in der Lage die (echt schwer zu verstehenden) Primärquellen selbst zu deuten und zu interpretieren.

    EIN RIESENGROßES DANKESCHÖN!

  7. Korrektur zu meinem Kommentar oben: Auch a^ib^ic^îd^ie^i ist noch eine gelinde kontextsensitive Sprache, es gibt da keine Beschränkung der Anzahl der Kopien. Was ich seinerzeit im Kopf hatte, ist TAG (tree adjoining grammars), einer der schwächsten etablierten Formalismen innerhalb der gelinde kontextsensitiven Sprachen. TAG kann in der Tat „nur bis vier zählen“.

  8. Nochmal zur Kontextfreiheit natürlicher Sprachen: genau genommen genügt eine kontextfreie Grammatik erst dann nicht mehr, wenn cross-serial dependencies UND Zentraleinbettungen (also die üblichere Konstruktion mit den geschachtelten Klammern) erlaubt sind. Nachgewiesen wurde das für Zürichdeutsch (nicht Schwyzerdütsch allgemein) und Brambara (eine Stammessprache in Mali), s. http://www.brawer.ch/prolog/sprachenhierarchie.pdf

  9. Das ist nicht richtig, Nicolas. Die oben von Herrn Rau erwähnte copy language zum Beispiel weist cross-serial dependencies und keine Zentraleinbettungen auf und lässt sich nicht mit einer kontextfreien Grammatik beschreiben.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.