andere "CB -> BC"-Umstellung auch möglich?

Question

Ist folgende Umstellung von CB -> BC legitim für kontextfreie Sprachen:

CB -> BB

BB -> BC

somit wäre die Hilfvariable in der Musterlösung überflüssig oder ?

 

Answer 1

Hallo,

mit den zwei Regeln könntest du Wörter mit der Grammatik erzeugen, die nicht in der Sprache sind.

Z.B. wäre die Ableitungsfolge

S -> aSBBCCC -> aabbCCCBBCCC -> aabbCCCBCCCC - >...

möglich, du hast dann also nicht mehr nur die reine Umsortierung sondern kannst auch "b's in c's" umwandeln (oder "c's in b's" wenn du deine erste Regel analog anwendest).

Viele Grüße

Christiane (Tutorin)