Definition Grammatik
An dieser Stelle wollen wir unsere bisherigen Überlegungen formalisieren. Betrachten wir unsere Eingangsbeispiele, so sehen wir bereits an der Form der Darstellung Unterschiede, nämlich zwei Arten von Kästchen, Kreise bzw. Ovale einerseits und Rechtecke andererseits. Die Zeichen oder Symbole in runden Kästchen sind Bestandteile unserer Sätze und werden nicht mehr verändert. Sie sind terminale Zeichen (Terminale; terminare (lat.) = abgrenzen, bestimmen, beendigen). Im Gegensatz dazu liegt noch kein Satz vor, wenn ein Gebilde noch Zeichen in eckigen Kästchen enthält. Diese müssen noch weiter erläutert, d. h. durch andere Zeichen ersetzt werden. Sie heißen deshalb nichtterminale Zeichen (Nichtterminale oder Variable). Die Regeln oder Produktionen des Beispiels sind durch die Syntaxdiagramme oder Ersetzungsregeln gegeben. Sie geben an, welche Ersetzungen zulässig sind. Schließlich muss noch das Ziel angegeben werden: In unserem Beispiel wollen wir Sätze bilden. Satz ist deshalb unser Startzeichen oder Startsymbol.
Diese vier Merkmale definieren eine Grammatik:
Definition: Grammatik
Eine Grammatik ist ein 4 Tupel G = (N, T, P, S) wobei gilt:
1. N ist eine endliche, nichtleere Menge, die Menge der nichtterminalen Zeichen,
2. T ist eine endliche, nichtleere Menge, die Menge der terminalen Zeichen,
3. P ist eine endliche Teilmenge von V* x V*, die Menge der Produktionen oder Regeln und
4. S \in N ist das Startzeichen.
Hinweis: In einigen Büchern findet die folgende Notation Anwendung: {G = (V_N, V_T, P, S)} oder auch {G = (V_N, V_T, R, S)}, d. h. N entspricht VN, T entspricht VT und R entspricht P.
Zudem gilt V = N \cup T die Menge der terminalen und nichtterminalen Zeichen und V* die Menge aller Worte, d. h. Zeichenketten, mit Zeichen aus V einschließlich des leeren Wortes \epsilon. Die Mengen N und T sollen disjunkt sein. V* x V* ist die Menge aller Wortpaare mit Worten aus V*. Eine Regel (u, v) bzw. {(u \rightarrow v)} ist so zu interpretieren, dass u überall, wo es als Teil eines Wortes auftritt, durch v ersetzt werden darf bzw. muss.
In unserem ersten Beispiel Umgangssprachliche Sätze gilt also die folgende Grammatik:
G = (N, T, P, S)
N = {Satz, Nominalphrase, Verbalphrase, Eigenname, Artikel, Substantiv, Verb}
T = {Susanne, Katze, Pferd, Heu, Buch, der, die, das, jagt, frisst, liest}
P = {(Satz -> Nominalphrase Verbalphrase .),
(Nominalphrase -> Eigenname | Artikel Substantiv),
(Verbalphrase -> Verb | Verb Nominalphrase),
(Eigenname -> Susanne),
(Substantiv -> Katze | Pferd | Heu | Buch),
(Artikel -> der | die | das),
(Verb -> jagt | frisst | liest)}.
S = SatzFormal können wir eine Ableitung bzgl. einer Grammatik G = (N,T,P,S) wie folgt definieren:
Ein Wort u \in V^{*} führt unmittelbar zu einem Wort v \in V^{*} oder v wird direkt aus u abgeleitet, kurz u \rightarrow v, genau dann, wenn es eine Regel (r_1, r_2) \in P gibt und Worte w_1, w_2 \in V^{*} mit u = w_1r_1w_2 und v = w_1r_2w_2. Das heißt, in u wird das Teilwort r_1 durch das Teilwort r_2 ersetzt.
Ein Wort u \in V^{*} führt zu einem Wort v \in V^{*} oder v wird aus u abgeleitet, kurz u \xrightarrow{*} v, genau dann, wenn es Worte w_1, w_2, ..., w_n \in V^{*} gibt mit u = w_1 \rightarrow w_2 \rightarrow ... \rightarrow w_n = v. Das heißt, es gibt eine endliche Folge von Ersetzungen, die von u zu v führt.
Definition Formale Sprache
Nun kann auch die zu G = (N,T,P,S) gehörende oder von G erzeugte Formale Sprache definiert werden:
L = L(G) = \{ w \in V_{T}^{*} \mid S \xrightarrow{*} w \}Das heißt, zu L gehören alle Worte, die nur aus terminalen Zeichen bestehen und die sich aus dem Startzeichen S mit Hilfe des Regelsystems P ableiten lassen.
Dabei bedeutet S \xrightarrow{*} w immer, dass es eine Ableitung von S nach w gibt. Wir haben damit aber noch kein Verfahren, um zu einer bestimmten Grammatik und einem bestimmten Wort festzustellen, ob dieses Wort in der von der Grammatik erzeugten Sprache liegt. Man kann sogar Grammatiken konstruieren, von denen man nicht weiß, ob die zugehörige Sprache überhaupt ein Element enthält.
Chomsky-Hierarchie Formaler Sprachen
Versuche, die Grammatik einer Sprache formal zu erfassen, gehen in die vorinformatische Zeit zurück und wurden von Linguisten durchgeführt. Einer von ihnen, Noam Chomsky, hat die möglichen Regelsysteme in vier Klassen eingeteilt (Chomsky-Hierarchie):
Sprachen vom Typ 3 oder reguläre Sprachen (u. a. links- bzw. rechtslineare Sprachen)
Sprachen vom Typ 2 oder kontextfreie Sprachen
Sprachen vom Typ 1 oder kontextsensitive Sprachen
Sprachen vom Typ 0 oder allgemeine Regelsprachen
Wir wollen uns hier an diese Klassen halten. Wir sind uns dabei bewusst, dass andere Einteilungen möglich sind und dass diese nicht notwendig mit der oben angegebenen verträglich sind.
Im Folgenden werden die einzelnen Klassen kurz erläutert (auch, wenn in anderen Beiträgen diese noch genauer erläutert werden).
Reguläre Sprachen (Sprachen vom Typ 3)
Zu dieser Klasse Sprachen gehören die linkslinearen und rechtslinearen Sprachen; beide sind äquivalent zueinander. In solchen Sprachen sind lediglich Ersetzungsregeln der Form A \rightarrow a, A \rightarrow B oder A \rightarrow Ba erlaubt.
Kontextfreie Sprachen (Sprachen vom Typ 2)
Alle Regeln sind von der Form A \rightarrow \alpha, d. h. ein Nichtterminalsymbol wird durch eine nichtleere Symbolfolge \alpha aus Terminal- und Nichtterminalsymbolen ersetzt. Bei dieser Ersetzung kommt es nicht auf den Kontext, die Umgebung von A an, A kann immer ersetzt werden, wie es auch auftritt. Ist A ein Teil von \alpha, so ist die Regel rekursiv.
Kontextsensitive Sprachen (Sprachen vom Typ 1)
Alle Regeln der Form \beta A \gamma \rightarrow \beta \alpha \gamma sind erlaubt. Ein Nichtterminalsymbol wird durch eine nichtleere Symbolfolge \alpha ersetzt, falls es im Kontext von \beta und \gamma auftritt.
Allgemeine Regelsprachen (Sprachen vom Typ 0)
Ohne alle Einschränkungen können nichtleere Teilworte durch andere ersetzt werden.
Seit Chomskys ersten Arbeiten war man der Auffassung, dass menschliche Sprachen mindestens so komplex wie die kontextsensitiven Sprachen sind. Das menschliche Sprachvermögen scheint durchaus mit noch komplizierteren Strukturen zurechtzukommen; andererseits ist es schwierig, in den natürlichen Sprachen echt kontextsensitive grammatische Formen zu finden. Dies kann als Hinweis dafür gelten, dass solche Strukturen von menschlichen Sprechern eher gemieden werden. Es gilt sogar für die echt kontextfreien Strukturen: Einbettungen treten kaum mehrfach ineinander geschachtelt auf; oft werden ihnen Ausklammerungen vorgezogen. Statt „Das Mädchen, das den Hund, der die Katze, die schnurrte, biss, sah, weinte.“ sagen wir: „Das Mädchen weinte, das den Hund sah, der die schnurrende Katze biss.“.
Ohne Schwierigkeiten kommt das menschliche Sprachvermögen offenbar nur mit dem einfachsten Sprachtyp, den regulären Sprachen, zurecht. Interessant dabei ist, dass die mathematische Klassifikation der Sprachen nach wachsender Komplexität, die aus rein theoretischer Erwägungen gewonnen wurde, sich auch für die menschliche Sprachfähigkeit als relevant erweist.
