Formale_Grammatik
Formale_Grammatik

== Die von einer Grammatik beschriebene Sprache ==
Eine Regel  einer gegebenen Grammatik  besagt, dass in einem Wort  mit R als Infix, R durch Q ersetzt werden kann, so dass ein neues Wort  mit  als Infix entsteht. Man spricht hierbei auch davon, dass  in  mit der Grammatik  bzw. durch die Regel  übergeht, oder auch, dass  aus  abgeleitet wurde. Dies kann durch   notiert werden (häufig auch  anstatt ). Soll nur ausgedrückt werden, dass in der Grammatik  das Wort  aus  entstehen kann, ohne eine Regel zu benennen, schreibt man stattdessen  (ist die Grammatik aus dem Kontext offensichtlich, auch einfach ). Demnach ist ein solcher Übergang von  in  eine Transitionsrelation, die eine natürliche Erweiterung von  auf alle möglichen -Kontexte darstellt, nämlich: 
wobei hier  die Konkatenation von Wörtern bezeichnet.
Gibt es nun eine Folge von Wörtern , bei der gilt, dass für jede natürliche Zahl  mit  das Wort  in  übergeht (), so ist  in  Schritten aus  ableitbar, was durch  dargestellt wird. Eine solche Wortfolge  wird ''Ableitung'' oder ''Rechnung'' von  in  der Länge  genannt. Weiterhin heißt  in  ableitbar, wenn es mindestens ein  gibt, so dass  in  Schritten aus  ableitbar ist. Wenn  in  ableitbar ist, so wird dies durch die Schreibweise  dargestellt. Dabei wird zusätzlich definiert, dass für jedes Wort  gilt, dass  ist, so dass die Relation  die reflexiv-transitive Hülle der Relation  ist.
Nun ist die von der Grammatik  erzeugte formale Sprache  diejenige Sprache, die aus allen Wörtern besteht, die zum einen nur aus Terminalsymbolen bestehen und die zum anderen vom Startsymbol mit einer endlichen Anzahl von Schritten abgeleitet werden können:
Dabei ist es egal, in welcher Reihenfolge die Produktionsregeln auf die abgeleiteten Wörter angewandt werden, oder ob es mehrere Möglichkeiten gibt, um ein Wort  aus  abzuleiten. Zwei Grammatiken  und  sind genau dann äquivalent, wenn die durch  und  erzeugten Sprachen gleich sind:
Wenn alle Terminalzeichen in den Wörten der formalen Sprachen vorkommen, dann müssen die Terminalzeichen übereinstimmen. Die Nichtterminalzeichen sind dagegen völlig frei.