Linkslineare Grammatik in rechtslineare Grammatik umwandeln

FisoDuck · Anmeldungsdatum: 27.06.2006 Beiträge: 3 Wohnort: Neumarkt

Hallo, ich habe folgendes Problem:
Gegeben sei folgende linkslineare Grammatik:

G = ({A, B, C, D}, {a, b, c, d, e}, A, P) mit den Produktionen P

P = { A -> Ade
A -> Be
A -> bc
B -> Bc
B -> C
C -> D
D -> Dab
D -> Ab}

Aus obiger Grammatik soll nun ein endlicher Automat erzeugt werden. Ich weiß wie man da vorgeht! NUR: Wie transformiere ich diese linkslineare Grammatik in eine Rechtslineare! Über eine Hilfestellung für diese Transformation wär ich dankbar.

Grüße FisoDuck

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Ich hatte grad viel groessere Probleme aus der linksregulaeren Grammatik einen Automaten zu basteln, als von dem Automaten zu einer rechtsregulaeren Grammatik zu kommen.

imho kann man die einfach aus dem Automaten ablesen.

Gruss,
ED

FisoDuck · Anmeldungsdatum: 27.06.2006 Beiträge: 3 Wohnort: Neumarkt

Hallo,
es ist aber verlangt, dass wir den Automaten über eine rechtslineare Grammatik konstruieren! Es soll über eine Chomsky-Grammatik konstruiert werden - leider fallen links-lineare Grammatiken nicht von Chomsky definiert!

Grüße FisoDuck

FisoDuck · Anmeldungsdatum: 27.06.2006 Beiträge: 3 Wohnort: Neumarkt

Hat keiner eine Idee, wie man da vorgeht?
MfG FisoDuck

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Ehrlich gesagt versteh ich das Problem nicht, was ist jetzt die genaue Aufgabenstellung?