Grammatiken

Grammatiken sind Gebilde, die zur Beschreibung von Wörtern bestimmter Sprachen dienen. Sie bestehen aus Regeln (Ersetzungsregeln, Produktionsregeln), die ihrerseits zwei Arten von Symbolen enthalten: Terminalsymbole, die in den Zeichenketten selbst vorkommen und Nonterminalsymbole (auch als Superzeichen oder Variablen bezeichnet), die nur zur Strukturbeschreibung benutzt werden.

Definition Grammatik

Eine Grammatik G ist ein Quadrupel G = (V_N, V_T, R, S) mit

V_n = Alphabet der Nonterminalsymbole
V_T = Alphabet der Terminalsymbole
R = Menge der Ersetzungsregeln der Form a->b , wobei aÎ(V*V_NV*) und bÍV*.
(Die linke Seite nennt man auch Prämisse und die rechte Seite nennt man Conclusio)
S = Satzsymbole (nennt man auch Axiom oder Startsymbol) aus V_n
Es ist: V_NÇV_T=Æ und V_NÈV_T=V

Betrachtet man die Menge der Ersetzungsregeln und ihre Art, so kann man die Grammatiken als rechtslinear, kontextfrei oder kontextsensitiv identifizieren. Demnach sind auch die so erzeugten Sprachen eingeordnet.

Da dies u.a. ein Thema der folgenden Vorlesungen sein wird, soll hier nicht näher darauf eingegangen werden.