Kontextfreie Grammatiken
Nicht alle Anforderungen und Probleme lassen sich mit formalen Sprachen so einfach lösen bzw. beschreiben. Man greift deshalb aus kontextfreie Grammatiken zurück, die eine Erweiterung der regulären Grammatiken darstellen.
Eine kontextfreie Grammatik G = (N, T, S, P) baut sich aus den vier folgenden Bestandteilen auf:
- N – ist ein Alphabet, dessen Elemente Nichtterminalsymbol heißen
- T – ist ein Alphabet, dessen Elemente Terminalsymbole heißen
- S – ist Element von N (also ein Nichtterminalsymbol und wird Startsymbol genannt
- P ⊆ N χ V* - ist eine endliche Menge von sogenannten Produktionen und es gilt V = N ∪ T
Auf der linken Seite einer Produktion darf immer nur ein Nichtterminalsymbol sein. Daraus ergibt sich, dass bei einem Ableitungsschritt nie ein Terminalsymbol ersetzt wird. Wo nämlich ein Terminalsymbol steht, „ist die Ableitung zu Ende“.