4-Tupel: G= (V, T, P, S) mit V ist endliche Menge der Variablen, T ist endliche Menge (Terminalalphabet). V geschnitten T ist die Leere Menge. P ist endliche Menge der Produktionen – formal: Teilmenge von (V vereinigt T)+ x (V vereinigt T)*. S ist Element von V und ist Startvariable.
Erzeugbare Sprache von G:
L(G) = { w Element von T* | S ->*G w }
->*G: reflexive und transitive Hülle von ->G
Beispiel:
G = ({E,T,F}, {(,),a,+,*}, P, E)
P = {E->T,
E->E+T,
T->F,
T->T*F,
F->a,
F->(E) }
„a * a * (a +a) + a“ wäre damit ein Element von L(G)
Ausgehend von der Startvariable kann man einen Baum mit möglichen Wörtern zeichnen (Blätter = Wörter). Es kann dabei unendlich lange Pfade geben und es kann auch Sackgassen geben, die sich nicht zu einem Terminalwort ableiten lassen.
Chomsky:
- Typ 0: alle Grammatiken
- Typ 1: heißt auch kontextsensitiv; wenn für w1->w2 in P gilt: |w1| < = |w2|
- Typ 2: heißt auch kontextfrei; wenn Grammatik von Typ 1 und falls für w1->w2 in P gilt: w1 ist eine einzelne Variable (also nicht zusammengesetzt)
- Typ 3: oder auch regulär; wenn Gramatik von Typ 2 und falls w2 entweder nur aus T oder einem Element aus T gefolgt von einem aus V
Es gibt Typ 0 Sprachen, die entscheidbar sind. Auf jeden Fall entscheidbar sind alle Typ 1-3 Sprachen. Entscheidbar heißt, es gibt einen Algorithmus, der in endlicher Zeit feststellt, ob ein Wort zu der Sprache gehört oder nicht.
Eine Grammatik heißt mehrdeutig, wenn es mehrere Syntaxbäume für ein und dasselbe Wort gibt, am sonsten heißt sie eindeutig. Eine kontextsensitive Sprache (Typ 1) heißt inhärent mehrdeutig, wenn es keine Möglichkeit gibt eine eindeutige Grammatik zu finden. Es ist i.A. nicht möglich durch einen Algorithmus Mehrdeutigkeit festzustellen.
Backus-Naur-Form (BNF):
Kompakte Beschreibung von Typ 2 Grammatiken
A->b1
A->b2
A->b3
wird: A-> b1|b2|b3
A->ac
A->abc
wird: A->a[b]c
A->ac
A->abc
A->abbc
A->ab….bc (oder: A->aBc, B->b, B->bB)
wird: A->a{b}c