====== Kontexfreie Sprachen ====== Eine Produktione heißt **kontextfrei** genau dann, wenn für jede Regel gilt: * Auf der linken Seite steht ein Nichtterminalsymbol. * Auf der rechten Seite steht ein beliebiges Wort bestehend aus Terminal und Nichtterminalsymbolen. 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 | ====== Kontextsensitive Sprachen ====== 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 * A ein Nichtterminalsymbol ist und * x und y beliebige Wörter bestehend aus Terminal- und Nichtterminalsymbolen sind. * w ein beliebiges, nicht-leeres Wort bestehend aus Terminal- und Nichtterminalsymbolen ist. 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.