Formale Sprachen: Chomsky Normalform

[vip*r]

Hi Leute!

Folgende Aufgabe:

Setzen sie diese Grammatik G in eine Chomsky-Normalform um:

$G=\{V,\Sigma,P,S\}$, $V=\{S,A,B\}$, $\Sigma = \{a,b\}$ $P =\{S\to ASA, S \to aB, A \to B, B \to b, B \to \epsilon\}$

Eliminierung der ε-Regeln:
P={
S->ASA
S->aB
A->B
B->b
S->a
A->ε}

Da hier jetzt eine weitere ε-Regel entstanden ist, muss ich nochmal anwenden:

P={
S->ASA
S->aB
A->B
B->b
S->a
S->SA
S->AS
S->S}

Eliminierung von Kettenregeln:

P={
S->ASA
S->ab
A->b
S->a
S->SA
S->AS}

Hierzu nun eine Frage: Die zwei Produktionen, die die Kettenregel ergeben, lauten: A->B und B->b. Muss ich nun jedes B auf der rechten Seite sämtlicher Regeln durch ein b ersetzen? Verändert sich dann auch die Regel S->aB zu S->ab? (Laut meinen Vorlesungsunterlagen schon, aber ich bin mir nicht sicher weil das sehr schwammig formuliert ist!) Die ursprüngliche Regel S->aB wird ersetzt, sprich sie verschwindet dann komplett, oder? Laut meinen Vorlesungsunterlagen gibt das dann aber einen Widerspruch. Eine CNF soll ja nur Produktionen enthalten die rechts ein Terminal oder zwei Variablen stehen hat. Das wäre aber dann hier mit meiner Produktion S->ab nicht mehr der Fall! Andersherum, wenn ich nicht jedes B auf der rechten Seite durch die Produktion B->b ersetze, handle ich zuwider der Eliminierung von Kettenregeln.

Die Regel S->S ist wohl sinnlos und kann sofort gestrichen werden. Gibt es noch weitere Kettenregeln, die ich hier eventuell übersehen habe?

Seht ihr mein Problem? Kann mir jemand helfen?