Eine Produktione heißt kontextfrei genau dann, wenn für jede Regel gilt:
Eine Grammatik heißt kontextfrei genau dann, wenn alle Produktionen der Grammatik kontextfrei sind.
Eine Sprache heißt kontextfrei genau dann, wenn sie mit Hilfe einer kontextfreien Grammatik beschrieben werden kann.
Eine Sprache ist kontextfrei genau dann, wenn sie von einem nichtdeterministischen Kellerautomaten erkannt wird. (deterministische erkenn nur eine echt Teilmenge der kontextfreien Sprachen)
Beispiel für eine kontextfreie Grammatik:
| A → B A → BA B → (C) B → (A) C → x |
Eine Produktion u → v heißt allgemein genau dann, wenn u und v beliebige Wörter aus Terminal- und Nichtterminalsymbolen sind.
Eine Produktion u → v heißt (Wortlängen-)monoton genau dann, wenn u und v beliebige Wörter aus Terminal- und Nichtterminalsymbolen sind und wenn v mindestens so lang wie ist.
Eine Produktion u → v heißt kontextsensitiv genau dann, wenn diese Produktion die Gestalt xAy hat, wobei
Beachte: Bei einer kontextsensitiven Produktion xAy → xwy darf das Nichtterminalsymbol A nur dann durch das Wort w ersetzt werden, wenn A im Kontext x..y steht. Beachte, dass die Wörter x und y auch das leere Wort sein können.
Beispiele:
| M → aM | allgemein, monoton, kontextsensitiv, kontextfrei, rechtslinear |
| S → bBS | allgemein, monoton, kontextsensitiv, kontextfrei, nicht rechtslinear |
| Aa → aA | allgemein, monoton, nicht kontextsensitiv, nicht kontextfrei, nicht rechtslinear |
Jede rechtslineare Produktion ist kontextfrei.
Jede kontextfreie Produktion ist kontextsensitiv.
Eine Grammatik heißt allgemein genau dann, wenn alle Produktionen allgemein sind.
Eine Grammatik heißt (Wortlängen-)monoton genau dann, wenn entweder alle Produktionen monoton sind, oder wenn alle Produktionen monoton sind außer S → λ, sofern das Startsymbol S nie auf der rechten Seite einer Produktion vorkommt. Eine Grammatik heißt kontextsensitiv genau dann, wenn entweder aööe Produktionen kontextsensitiv sind, oder wenn alle Produktionen kontextsensitiv sind außer S → λ, sofern das Startsymbol S nie auf der rechten Seite einer Produktion vorkommt. Eine Sprache heißt monoton / kontextsensitiv** genau dann, wenn sie von einer monotonen / kontextsensitiven Grammatik erzeugt wird.