Rechtslineare in Linkslineare Grammatik umwandeln

[Codewalker]

Ich hoffe hier ist noch jemand, der sich mit Grammatiken und formalen Sprachen rumschlagen darf. Ich suche ein Verfahren, um aus einer rechtslinearen, eine linkslineare Grammatik zu bauen. Wikipedia sagt nur, dass es geht, aber nicht wie. Kann jemand helfen?

[JasonDX]

Einen spezifischen Algorithmus dafür kenne ich nicht - das theoretisch einfachste, das mir in den Kopf gekommen ist, wäre eine rechts(links)lineare Grammatik in einen Automaten zu überführen, und dann den Automaten in eine links(rechts)lineare Grammatik zurückzuführen.
Die Überführung einer rechtslinearen Grammatik in einen Automaten ist dabei relativ einfach:
Gegeben ist eine Grammatik mit den Nonterminalen X_1..X_n über dem Alphabet a_1..a_m und den Produktionen P. Daraus wird ein Automat berechnet:
Das Alphabet bleibt das selbe, die Zustände sind die X_1..X_n plus ein Endzustand Y; Startzustand ist das Startterminal der Grammatik, Endzustand ist der eigens eingeführte Zustand Y.
Die Transition wird für jeden Zustand wiefolgt berechnet:
Für jede Produktion X -> a_i X_j wird im Zustand X eine Transition mit a_i zum Zustand X_j hinzugefügt. Für Produktionen der Form X -> a_i wird eine Transition vom Zustand X mit a_i nach Y hinzugefügt. Damit ergibt sich ein NFA, aus dem man dann eine linkslineare Grammatik errechnen kann:
Das Alphabet bleibt wiederum gleich, die Nonterminale sind die Zustände des Automaten X_1..X_n + Y; Startproduktion ist Y, und die Produktionen werden folgendermaßen bestimmt:
1. Für jede Transition von einem Zustand X_i mit a_j nach X_k wird die Produktion X_k -> X_i a_j eingeführt.
2. Sei X_i der Startzustand des Automaten, dann wird X_i -> e zu den Produktionen hinzugefügt. (Bzw. für jede Produktion X_k -> X_i a_j die Produktion X_k -> a_j hinzugefügt).

Ein Beispiel (Die Grammatik macht übrigens keinen Sinn ):
Gegeben ist die rechtslineare Grammatik G = ({ A, B }, { a, b, c }, P, A) und den Produktionen P:
A -> bA | aB
B -> cA | c

Daraus entsteht der Automat mit Mg = ({ A, B, Y }, { a, b, c }, d, A, Y) mit den Transitionen d:
d(A, a) = { B }
d(A, b) = { A }
d(B, c) = { A, Y }

Daraus können wir dann die linkslineare Grammatik Gm = ({ A, B, Y }, { a, b, c }, P, Y) errechnen:
Y -> Bc
B -> Aa
A -> Ab | Bc | e
Bzw. ohne Epsilonproduktion:
Y -> Bc
B -> Aa | a
A -> Ab | b | Bc


Evt. ließe sich das ganze mit den First&Follow-Sets aus CFGs einfacher durchführen, aber so wird die Idee hinter dem Algorithmus etwas klarer

greetz
Mike