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 aⁱbⁱcⁱ, 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.