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

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.