Übersetzen eine rechte rekursive Grammatik in Chomsky Normalform

Question

Ich versuche, eine Übung zu tun, wo ich eine Grammatik in Chomsky Normalform übersetzen. Ich verstehe, wie dies unter normalen Umständen zu tun, aber dieses Mal die Grammatik arbeite ich mit richtig ist rekursiv. (Technisch gesehen die Grammatik ist die Antwort auf die vorherige Frage, so dass ich nur die falsche Gamma haben könnte.)

Ich glaube, ich kann dies tun, indem eine feste Abfolge von Regeln anstelle von e-Regeln verwenden, aber ich mag sicherstellen, ich bin Position nicht in der falschen Richtung. Es ist einfacher, mit einem Beispiel zu erklären:

Für eine Grammatik, die n ‚a des erzeugt, wobei n größer als 0 und ein Vielfaches von drei: (Keine Sorge, das ist völlig anders als die Grammatik meiner eigentlichen Übung)

S-> Aaaa
A-> Aaaa
A-> ε

wäre die richtige Übersetzung sein:

S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a

Answer 1

Auch wenn Ihre Grammatik rechts rekursiv ist, können Sie die Chomsky Normalform Transformation ausführen wie jede andere (nicht rechts rekursiv) Grammatik. Folgen Sie einfach dem Algorithmus in Ihr Buch beschrieben, das wahrscheinlich aus zwei Schritten besteht: (1) ersetzt alle Vorkommen von Terminals a durch Regeln A -> a , wobei A tritt nicht in dem Regelsatz; (2) transformieren alle Regeln . A -> w , wobei len (w)> 2, durch Regeln der Länge 2 mit frischem Variablen

Für Ihre A Regel dann, bauen eine Regel für die Ableitung Terminals, sagen K -> a und ersetzen Sie alle Vorkommen des Anschlusses a :

A -> AKKK

Dann legen Sie die Grammatik in CNF

A    -> AA'
A'   -> KA''
A''  -> KK