Rechtslineare Grammatik in linkslineare Grammatik umwandeln

Moeki · Gast

Hallo Freunde der theoretischen Informatik.

Wir haben eine Typ 2 Grammatik in eine rechtslineare Grammatik umgewandelt und einen äquivalenten e-NEA erstellt. Wie ist nun das Prozedere, wenn ich aus der rechtslinearen Grammatik eine linkslineare Grammatik machen möchte?

Leider finde ich dazu keine Informationen im Skript, diversen Büchern und im Internet.

Muss ich mich im e-NEA vom Endzustand zum Startzustand zurückarbeiten und dementsprechend eine Terminalvariable mit der Startvariable tauschen oder wie funktioniert das? Eine genaue Formulierung würde mir bestimmt sehr weiterhelfen.

Danke,
Moeki.