Man vermutet, daß es entscheidbar ist, ob ein Wort-Ersetzungs-System mit nur einer Regel unendliche Ableitungen besitzt oder terminiert. Das gründet sich auf eine andere Vermutung, nach der jedes nicht terminierende System dieser Art eine Schleife, d. h. eine Reduktion u ->> p u q gestattet. (Zum Beispiel gestattet ba -> aabb die Schleife bba -> baabb -> aabbabb = aa bba bb.)
Diese Vermutung würde erhärtet, falls Nachfolgermengen solcher Systeme immer kontextfrei wären, denn die Schleife könnte man dann aus dem Pumping-Lemma ablesen. (Die Nachfolgermenge von bba im Beispiel ist kontextfrei.)
Wir zeigen jedoch, daß die Menge der Nachfolger von baba unter der Regel ba -> aabb nicht kontextfrei ist. Dabei benutzen wir spezielle 3x3-Matrizen, um Wortlängen zu zählen. Wir hoffen, daß dieses Verfahren auch für andere Ein-Regel-Systeme interessante Aussagen liefert.
Ein Wort ist primitiv, wenn es kein Vielfaches eines kürzeren Wortes ist - abbab ist primitv, aber abbabb = (abb)^2 nicht.
Dabei gehe ich auf einige Pump-Eigenschaften ein, die die Sprache Q erfüllt - die also leider nichts zur Lösung des Problems beitragen.