Einfach gesagt
Eine Grammatik ist eine explizite Erzeugungsmöglichkeit für eine Formale Sprache. Ihre Struktur bildet sich aus expliziter Ableitung von Wörtern aus Regeln.
Eine Grammatik
ist die endliche Varablenmenge (Nichtterminale) ist das endliche Terminalalphabet mit ist die endliche Menge von Produktionen (Produktionsregeln) ist das Startsymbol
Anmerkungen
Auf der linken Seite dürfen auch Kombinationen aus Nichtterminalen oder Nichtterminalen und Terminalen stehen, z.B.:
Es ist möglich, dass man beim Ableiten auf “Sackgassen” stoßen kann, an denen man zwar noch nichtterminale hat, es aber keine möglichen Ableitungsregeln mehr gibt
Verwandt: Algorithmus: Worterzeugung, Eindeutige Grammatik, Chomsky-Hierachie