Formale Grammatik

Eine formale Grammatik ist ein formales System das Sprachen beschreiben und generieren kann. Eine formale Grammatik besteht immer aus dem vierer-Tupel:

-       Menge der Nonterminalsymbole N

-       Menge der Terminalsymbole T

-       Regelmenge P

-       Startsymbol S

Eine formale Grammatik umfasst also ein Vokabular, eine Regelmenge und ein Startsymbol S. Eine formale Grammatik erzeugt eine formale Sprache. Formale Grammatiken sind vom Typ 0 bzgl. der Chomsky-Hierachie.

Das Vokabular einer formalen Grammatik besteht aus Nonterminalsymbolen und Terminalsymbolen. Nonterminalsymbole werden grob gesagt als Übergangssymbole verwendet.

Gemäß der Produktionsregeln aus der zu der Grammatik gehörenden Regelmenge lassen Sich die Nonterminalsymbole auf Nonterminalsymbole, Terminalsymbole oder das leere Wort ableiten. Durch solche Ableitungen entstehen ausgehend von dem Startsymbol und gemäß der vorgegebenen Produktionsregeln der Regelmenge Wörter. Die Menge aller durch die Grammatik erzeugbaren Wörter werden als durch die Grammatik erzeugte Sprache bezeichnet. Ein Wort besteht jedoch nur aus zusammengesetzten Terminalsymbolen, oder aus dem leeren Wort. Somit erklärt sich auch die Sichtweise, dass Nonterminalsymbole als Übergangssymbole betrachtet werden können. Nonterminalsymbole einer formalen Grammatik, also einer Grammatik vom Typ 0 der Chomsky-Hierachie, müssen irgendwann entweder auf das leere Wort oder auf ein Terminalsymbol abgeleitet werden.

Eine formale Grammatik unterliegt keinen Einschränkungen.