Kleines Nachschlagewerk Informatik
Rekursiv aufzählbare Sprachen
Worum geht es?
Kontextsensitiv Sprachen erlaubten bereits recht viele Arten von Produktionsregeln. Allerdings gab es noch eine Einschränkung: rechts durften nicht weniger Symbole stehen als links. Diese Monotonie genannte Einschränkung wird nun aufgehoben.
Produktionsregeln
Es gilt wieder, dass links jede mögliche Kombination aus Terminal- und Nichtterminalsymbolen stehen darf, sofern mindestens ein Nichtterminalsymbol enthalten ist. Die rechte Seite darf aber kürzer sein.

Somit sind Produktionsregeln wie

      xAy -> A
            
möglich.
Beispiel
Hat jemand ein schönes Beispiel? Her damit!