| |
|
| Table of contents |
|
2 Von erzeugte Sprache 3 Beispiel |
Eine formale Grammatik ist ein 4-Tupel, bestehend aus einer endlichen Menge von Nichtterminalsymbolen (im Folgenden kurz Nichtterminale, oft aber auch Variablen genannt), einer endlichen Menge von Terminalsymbolen (im Folgenden kurz Terminale genannt) (wobei das Alfabet und die Nichtterminale N disjunkt sind), einer endlichen Menge von Produktionsregeln (im Folgenden kurz Regeln, oft auch Produktionen, genannt) und einem Startsymbol , welches zu den Nichtterminalen gehört:
, ,
Nichtterminale werden gewöhnlich durch Großbuchstaben, Terminale durch Kleinbuchstaben repräsentiert.
Eine Regel besteht aus einer linken und einer rechten Seite, die jeweils ein Wort bestehend aus Terminalen und Nichtterminalen sind. Die rechte Seite kann dabei im Gegensatz zur linken Seite auch das leere Wort (im Folgenden mit symbolisiert) sein, also das Wort, welches keine Symbole enthält:
Eine Folge von Anwendungen solcher Regeln bezeichnet man als Ableitung, siehe dort.
Eine Grammatik erzeugt eine formale Sprache , die aus allen Wörtern besteht, die nur aus Terminalen bestehen und vom Startsymbol abgeleitet werden können:
Wir betrachten die Grammatik mit den Terminalen , den Nichtterminalen mit dem Startsymbol und den Regeln
Hierbei ist zu beachten das dies nicht die einzige Grammatik ist, die diese Sprache erzeugt. Eine weitere Grammatik zur Erzeugung von ist die mit diesen Regeln
Man klassifiziert verschiedene Typen von Grammatiken in der so genannten Chomsky-Hierarchie.
Definition
Eine Regel kann auf ein Wort, bestehend aus Terminalen und Nichtterminalen, angewendet werden, wobei ein beliebiges Vorkommen der linken Seite der Regel im Wort durch die rechten Seite der Regel ersetzt wird. Für solche Produktionen hat sich folgende Schreibweise eingebürgert:Von erzeugte Sprache
symbolisiert hierbei die so genannte Transitionsrelation, siehe dort.
Beispiel
Sie definiert die Sprache aller Wörter der Form , d.h. Kopien von gefolgt von Kopien von .
Man sieht also das es zur Erzeugung einer Sprache mehrere (genaugenommen: beliebig viele) Grammatiken gibt.