Linkslineare zu Rechtslineare Grammatik

[b1zarRe]

Hi,

Leider hänge ich am Thema Grammatiken, und vielleicht hat jemand ja ein Tipp:
Ich habe folgenden Automaten: http://www7.pic-upload.de/22.08.11/lx8ju3lucn9.jpg

Dieser erkennt Testwörter: a,ab
und die (rechtslinearen)Produktionen des DFAs sind:

Grammatik R:
S0 -> a S1
S1 -> b S2
S1 -> epsilon
S2 -> epsilon

Daraus lässt sich auch problemlos das Wort ab oder a ableiten.
Nun möchte ich hieraus eine Linklineare Grammatik konvertieren, jedoch bin ich da auf das Problem gestoßen, wie ich den Zustand S1 als Produktion darstellen soll...:

Das Problem ist, dass wenn ich ich die Grammatik umkonventiere wie ich es gelernt habe, dann klappt zwar das Testwort ab noch, aber nichtmehr nur a... weil wenn das klappt klappt dann klappt auch nur b was nicht klappen darf... Ich hoffe das ist halbwegs verständlich...?

Was mache ich da falsch???

 

[SlaterB]

mit einer Regel die ein b erzeugt musst du eben in einen Zustand gelangen, von dem aus zwingend noch ein a erforderlich ist, dieser Zustand darf kein Endzustand sein,
wie lauten denn deine Konstruktionsregeln im Original?

für das Bild stelle dir vor:
gehe von den bisherigen Endzuständen zum einzigen Startzustand S0, dem neuen Endzustand,
wenn du von S2 aus die b-Regel anwendest, landest du in S1, welches hier kein Endzustand ist, nur S0,
also muss von S1 zwingend noch mit a zu S0 gegangen werden,

nur der Anfang sieht dann bisschen anders aus, so dass du letzlich wohl nicht mit diesem Bild an sich zurechtkommt,
du brauchst gewiss einen einzigen Startzustand?

 

[b1zarRe]

Naja, die linkslineare Grammatik müsste (nach gesundem Überlegen) folgende sein:

S2 -> S1 b
S1 -> S0 a
S0 -> Epsilon

mit Anfangszuständen S2 sowie S1... Also sprich, die Endzustände von der rechtsl. Grammatik sind wohl die Anfangszustände der linklinearen Grammatik und der Endzustand der links. Grammatik ist wohl der Anfangszustand der rechts. Grammatik.

right?

 

[Marcinek]

Also normalerweise hast du nur einen Anfangszustand.

Ich würde dann für diese Sprache sowas vorschlagen

S => A a | B b
A => epsilon
B => A a

 

[b1zarRe]

Ok verstehe... aber das war auch einfach nach "klugem" Denken und betrachten des DFAs oder? Oder nach einer exakten Methodik rechtslinear in linkslinear umwandeln???