Sprachen wie Deutsch, Französisch, Englisch oder Latein kennt jeder. Wir wissen auch, dass diese Sprachen keineswegs formlos sind. Wenn wir feststellen wollen, ob ein gegebener umgangssprachlicher Satz formal korrekt ist, so prüfen wir dies anhand der Grammatik. Allerdings kann die Frage nach der grammatischen Korrektheit nicht immer eindeutig beantwortet werden. So heißt es z. B. in der Duden-Grammatik zur Verwendung des Kommas: „Gelegentlich ist es dem Schreibenden freigestellt, ob er einen Satzteil als Einschub werten will oder nicht.“ Bei der Definition künstlicher Sprachen – wie z. B. einer Programmiersprache oder der Formelsprache der Mathematik – werden solche Unsicherheiten nach Möglichkeit ausgeschlossen.

Beispiel 1: Umgangssprachliche Sätze

Problemstellung

Wir wollen einen kleinen Ausschnitt der deutschen Sprache untersuchen, und zwar Sätze der Form: „Die Katze jagt.“, „Das Pferd frisst das Heu.“, „Susanne liest das Buch.“. Was ist diesen Sätzen hinsichtlich ihrer grammatischen Struktur gemeinsam? Nun, jedem liegt die Grundstruktur Subjekt – Prädikat – Objekt zugrunde, wobei die Verwendung des Objekts optional ist. Ein Subjekt kann aus einem Artikel in Verbindung mit einem Substantiv oder einem Eigennamen bestehen; Prädikate bestehen aus Verben. Objekte können ebenfalls aus einem Artikel in Verbindung mit einem Substantiv oder einem Eigennamen bestehen oder ganz weggelassen werden. Da Subjekte und Objekte gleichartig definiert sind, lassen sie sich in der Kategorie Nominalphrase zusammenfassen. Jeder Satz besteht somit aus einer Nominalphrase, die durch eine Verbalphrase (Prädikat – Objekt) zu einem vollständigen Satz ergänzt wird.

Syntaxdiagramm

Diese Struktur lässt sich mithilfe von Syntaxdiagrammen in einer einfachen Form definieren:

Außerdem gibt es noch ein kleines Lexikon, welches uns den Wortschatz für unsere Sprache liefert. In der Umgangssprache liegt er bei etwa tausend, insgesamt in einer Sprache bei einigen zehntausend Worten und entzieht sich damit in der Praxis einem Regelwerk. Daher kann man eine natürliche Sprache nicht formal fassen. Für unser Beispiel sollte allerdings der folgende Wortschatz genügen:

Wir sehen, dass zwei verschiedene Arten von Symbolen in den Syntaxdiagrammen Anwendung finden: Rechtecke und Ovale. In den Ovalen stehen Zeichen bzw. Worte, die zum Alphabet der Sprache gehören; solche Zeichen nennen wir zukünftig Terminale. Die Bezeichnung „terminal“ weist darauf hin, dass es sich sozusagen um endgültige Zeichen handelt. Mit den Rechtecken werden sogenannte Nichtterminale bezeichnet. Diese treten nur innerhalb einer Herleitung auf, nicht jedoch in der endgültig abgeleiteten Zeichenfolge.

Grammatikregeln

In Form einer Grammatikregel wird der Sachverhalt folgendermaßen definiert:

SATZ -> NOMINALPHRASE VERBALPHRASE .

Den Pfeil lesen wir als „besteht aus“ oder „kann ersetzt werden durch“. Die Regel legt also fest, dass ein Satz aus einer Nominalphrase und einer Verbalphrase besteht. In dieser Form lassen sich nun auch die weiteren Regeln für unsere Grammatik formulieren:

NOMINALPHRASE -> EIGENNAME
NOMINALPHRASE -> ARTIKEL SUBSTANTIV
VERBALPHRASE -> VERB
VERBALPHRASE -> VERB NOMINALPHRASE
EIGENNAME -> Susanne
SUBSTANTIV -> Katze | Pferd | Heu | Buch
ARTIKEL -> der | die | das
VERB -> jagt | frisst | liest

Die Regeln für (z. B.) Substantiv wurden zu einer Regel zusammengefasst; mehrere mögliche Ersetzungen können durch ein | („pipe“) voneinander getrennt angegeben werden. Für die Schreibweise wird vereinbart: Nichtterminale werden in Großbuchstaben geschrieben, Terminale „normal“.

Die Gesamtheit der Ersetzungsregeln (einschließlich des Lexikons) heißt Grammatik. Sie dient dazu, grammatisch korrekte Sätze zu erzeugen. Dies geschieht durch schrittweise Herleitung mithilfe der Regeln.

Ableitung eines Satzes

Es ist der Satz „Susanne liest das Buch.“ abzuleiten. Die Ableitung eines Satzes geschieht dadurch, dass jeweils der linke Teil einer Regel durch deren rechten Teil ersetzt wird, wobei stets mit SATZ zu beginnen ist:

SATZ \Rightarrow NOMINALPHRASE VERBALPHRASE .
     \Rightarrow EIGENNAME VERBALPHRASE .
     \Rightarrow Susanne VERB NOMINALPHRASE .
     \Rightarrow Susanne liest ARTIKEL SUBSTANTIV .
     \Rightarrow Susanne liest das Buch .

Den Pfeil lesen wir als „wird ersetzt durch“. Wir haben zwischen die Worte einige Leerzeichen eingefügt, damit wir sie mit dem Auge besser trennen können. Dieses Beispiel (und auch „Das Pferd frisst Heu.“, „Susanne jagt die Katze.“ usw.) zeigt, dass unser Regelwerk eine gewisse Berechtigung hat. Es lassen sich aber auch andere Sätze nach diesen Regeln bilden, die uns wenigstens merkwürdig, wenn nicht sinnlos erscheinen: „Das Buch jagt die Katze.“, „Susanne liest das Pferd.“ oder „Das Heu frisst das Pferd.“

Hierbei erkennen wir, dass zum formalen Aspekt einer Sprache, der Syntax, ein inhaltlicher hinzukommt, die Semantik. Es gibt einige Versuche, auch die Semantik einer Sprache formal zu fassen. Die Ergebnisse sind für uns an dieser Stelle allerdings nicht darstellbar. Systeme wie Alexa, Siri o.ä. arbeiten mit deklarativen Programmiersprachen und mit großen Wissensbasen, die die semantischen Verknüpfungen immer besser erfassen.. Wir wollen diesen Aspekt ganz aus den weiteren Überlegungen ausschließen und uns nur auf die Syntax beschränken.

Beispiel 2: Wohlgeformte Klammerterme

Lassen wir in einem – korrekt gebildeten – arithmetischen Term (Rechenausdruck) die Zahlen und Buchstaben weg, d. h. betrachten wir nur die Klammern, so erhalten wir Zeichenfolgen der Form (), ()() oder (()(())); wir nennen sie wohlgeformte Klammerterme. Ein solcher Term muss gleich viele öffnende wie schließende Klammern enthalten, und an keiner Stelle darf die Anzahl der schließenden die der öffnenden Klammern überschreiten. Die Grammatikregeln zur Erzeugung wohlgeformter Klammerterme lauten wie folgt:

S -> ()
S -> (S)
S -> SS

… oder auch zusammengefasst …

S -> () | (S) | SS

Die dritte Regel dient dazu, Klammerterme aneinanderzureihen; die zweite Regel erlaubt eine rekursive Verschachtelung von Klammern und die erste Regel gewährleistet einen Abbruch des Erzeugungsvorgangs. Zur Herleitung (Erzeugung) der Zeichenfolge (())(()()) können wir folgende Ersetzungen vornehmen:

S \Rightarrow SS \Rightarrow (S)S \Rightarrow (())(S) \Rightarrow (())(SS) \Rightarrow (())(()S) \Rightarrow (())(()())

Beispiel 3: Ausgewogene Bitmuster

Wir betrachten die Sprache über dem Alphabet {0,1}, bei der jedes Wort gleich viele Nullen wie Einsen enthält (z.B.: 01, 10, 001011, 1000011011). Immer, wenn eine Null erzeugt ist, müssen wir uns merken, dass zum Ausgleich noch eine Eins anzufügen ist; entsprechendes gilt für die Einsen. Als Nichtterminalzeichen verwenden wir S, A und B, wobei S das Startzeichen ist, d. h. aus S sollen alle Wörter der Sprache hergeleitet werden können. Aus A sollen alle Wörter hergeleitet werden, die eine Eins mehr als Nullen enthalten; entsprechend für B. Diese Überlegung führt zur Grammatik mit folgenden Ersetzungsregeln:

S -> 0A | 1B
A -> 1 | 1S | 0AA
B -> 0 | 0S | 1BB

Betrachten wir eine Ableitung:

S \Rightarrow 1B \Rightarrow 11BB \Rightarrow 11B0 \Rightarrow 110S0 \Rightarrow 1100A0 \Rightarrow 110010

Nun gibt es andere Ersetzungsregeln, mit denen sich genau die gleichen Worte wie im obigen Beispiel herleiten lassen. Folgende Überlegung hilft uns dabei weiter: Die Wörter 01 und 10 sind hinsichtlich 0 und 1 ausgewogen. Wenn X und Y ausgewogen sind, dann auch XY (d. h. erst X, dann Y). Ist X ausgewogen, so sind es auch 0X1 und 1XO. Hieraus lassen sich folgende Ersetzungsregeln gewinnen:

S -> 01 | 10 | SS | 0S1 | 1S0

Nun wollen wir das gleiche Wort wie oben ableiten:

S \Rightarrow 1S0 \Rightarrow 1SS0 \Rightarrow 1S010 \Rightarrow  110010

Zwei solche Grammatiken, die die gleiche Sprache erzeugen, nennt man äquivalent.

Schlagwörter: