Chomsky Normalform

Drys@k · Anmeldungsdatum: 13.05.2006 Beiträge: 5

Hallo Leute,

ich möchte folgende Grammatik in die CNF überführen..

G = ({A,B},{a,b},P,A)

P = {A->AB |B, B->aAb| bAa | ab | ba}

das sollte auch eigentlich kein Problem sein...
wenn da nicht die Regel A-> AB | B wäre !!!!

Was mache ich mit A -> B ?? wie ersetzte ich B ???
Ich kann B ja z.B. nicht durch XY ersetzen oder ??

ein zirkuläre Bezug ist es ja auch nicht, da dafür die Regel B -> A fehlt....

Also bitte helft mir und gibt mir einen Tipp... Hilfe

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Wenn man A -> B hat und B -> C dann kann man dann kann man B (in diesem Fall) ja ganz weglassen indem man direkt A -> C schreibt. Sowas muesste dann auch bei deiner Chomsky Normalform gehen, denke ich.

Gruss
ED