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 = (VN, VT, R, S) mit
- Vn = Alphabet der Nonterminalsymbole
- VT = Alphabet der Terminalsymbole
- R = Menge der Ersetzungsregeln der Form a->b , wobei aÎ(V*VNV*) 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 Vn
- Es ist: VNÇVT=Æ und VNÈVT=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.