ich möchte an einem beispiel schritt 2 und 3 der chomsky-normalform machen. kann mir einer sagen, ob das richtig ist?

ursprüngliche produktionen:

S->ABD
A->ED|BB
B->AC|lambda
C->lambda
D->d
E->e

nach lambda-elimination:

S->ABD|BD|AD|D
A->ED|BB|B
B->AC|C|A
D->d
E->e

und nun nach reduzieren (schritt 2):

S->ABD|BD|AD|D
A->ED|BB|B
B->A
D->d
E->e

stimmt das??

kettenregeln entfernen (schritt 3):

S->ABD|BD|AD|d
A->ED|BB|B
B->A
D->d
E->e

stimmt das??

ersetzen langer terminalregeln (4.schritt):

S->ABD|BD|AD|d
A->ED|BB|B
B->A
D->d
E->e also gar nichts verändern? stimmt das??

und wie würde verkürzen zu langer regeln (schritt 5) gehen?
wenn das ein ungünstiges beispiel ist, würde ich mich freuen, wenn ihr für schritt 3 bis 5 (oder 6) beispiele aufschreiben würdet!
danke!

Hmmhmm, in CNF ist es ja noch nicht, da S -> ABD ist.
Die Frage ist, was man mit dem Burschen macht?
Vielleicht
S -> EDBD | BBBD | BBD usw…
Wer weiß :-)

Hmmhmm, in CNF ist es ja noch nicht, da S -> ABD ist.
Die Frage ist, was man mit dem Burschen macht?
Vielleicht
S -> EDBD | BBBD | BBD usw…
Wer weiß :-)

so gehts: (also einfach ein neues nt G einführen)

S -> AG|BD|AD|d
G -> BD

ah, und das machen wir warum? weil ABD zu lang ist?
stimmen denn meine schritte 2-4?

Die anderen Schritte stimmen soweit ich das beurteilen kann
ABC ist zu lang ja, weil CNF bedeutet, dass jede Produktion in 2 Nonterminale übergeht oder genau ein Terminal

Was ist eigentlich mit
A->B
B->A
CNF ist das auch noch nicht.
Was kann man damit machen?

ah, und das machen wir warum? weil ABD zu lang ist?

ja es muss immer entweder "nt -> nt nt" oder "nt -> t" sein in der cnf alles andere ist da nicht erlaubt

stimmen denn meine schritte 2-4?

mh irgendwie nich

S->ABD
A->ED|BB
B->AC|lambda
C->lambda
D->d
E->e

lambda-prod: B,C,A

S->ABD|BD|AD|D
A->ED|BB|B
B->AC|C|A
D->d
E->e

nicht produktiv: C

S->ABD|BD|AD|D
A->ED|BB|B
B->A
D->d
E->e

1. schritt: kettenregeln entfernen

S->AAD|AD|d
A->ED|AA
D->d
E->e

2. schritt: neue terminalproduktionen

braucht man hier nichts machen..

3. schritt lange produktionen kürzen

S->AG|AD|d
A->ED|AA
D->d
E->e
G->AD

(glaub ich..)

Hmm was will man mit einer Grammatik die kein Wort erzeugt, weil kein Terminalsymbol vorkommt?
Ist ja auch egal was man damit macht, die erzeugte Sprache ist immer die leere Menge dann
Oder worauf willst du hinaus?

Was ist eigentlich mit
A->B
B->A
CNF ist das auch noch nicht.
Was kann man damit machen?

naja das bedeutet ja genau dass A und B das gleiche ist (man kann ja beliebig dazwischen wechseln) also wird das zu einem zusammengefasst.

S->ABD|BD|AD|D
A->ED|BB|B
B->A
D->d
E->e

1. schritt: kettenregeln entfernen

S->AAD|AD|d
A->ED|AA
D->d
E->e



-> ah, okay. Wenn man das so machen darf, dann kommt man auf CNF.
Aber darf man B->A einfach dann weglassen?

Jo Brokkoli hat recht, hab die Kettenregeln übersehen, aber ich hab dann auch nochmal ne Frage:
Folie 960 bei F2 da wird vom Startsymbol alles verkürzt bis auch nur ein Nonterminal noch vorkommt, warum bei dieser Grammatik nicht?
Werden nur Kombinationen aus Nonterminalen benutzt, in welchen wenigstens eins auf ein Terminal abgebildet werden kann?
Würde hier ja erklären, warum S nicht nach nur A oder nur B geht

S->ABD|BD|AD|D
A->ED|BB|B
B->A
D->d
E->e

1. schritt: kettenregeln entfernen

S->AAD|AD|d
A->ED|AA
D->d
E->e



-> ah, okay. Wenn man das so machen darf, dann kommt man auf CNF.
Aber darf man B->A einfach dann weglassen?

also eigentlich gehört das so:

S->ABD|BD|AD|D
A->ED|BB|B
B->A
D->d
E->e

1. schritt: kettenregeln entfernen

S->ABD|BD|AD|d
A->ED|BB
B->ED|BB
D->d
E->e

aber weil die eben genau das gleiche produzieren hab ich die zu einem zusammengefasst..

Jo Brokkoli hat recht, hab die Kettenregeln übersehen, aber ich hab dann auch nochmal ne Frage:
Folie 960 bei F2 da wird vom Startsymbol alles verkürzt bis auch nur ein Nonterminal noch vorkommt, warum bei dieser Grammatik nicht?
Werden nur Kombinationen aus Nonterminalen benutzt, in welchen wenigstens eins auf ein Terminal abgebildet werden kann?
Würde hier ja erklären, warum S nicht nach nur A oder nur B geht

du musst ja erstmal alle lamda-produktionen raussuchen, das sind da A,B,S und hier sind es eben nur A,B,C

1. schritt: kettenregeln entfernen

S->AAD|BD|AD|d
A->ED|BB
B->ED|BB
D->d
E->e

da ist dir jetzt aber ein kleiner schreibfehler passiert:

S->ABD|BD|AD|d
…

da ist dir jetzt aber ein kleiner schreibfehler passiert:

S->ABD|BD|AD|d
…

ups :D (habs nun geändert)
das kommt davon wenn man zuviel copy&paste macht *g*

Ahhh, hat n Augneblick gedauert bis ich begriffen hab was du meinst :)))
Weil D nicht in der Menge ist, muss D in jeder Prod vorkommen, ist das die Aussage deines posts?

ja ;)

Warum auch einfach wenns kompliziert geht :D

A->ED|AA
Könnte man nicht auch
A->ED
schreiben?

Nein, denn wenn du A –> AA abbildest und danach beide A´s auf ED würde aus einem A aufeinmal EDED werden. Das kannste so häufig wiederholen wie du willst, daher muss das AA da stehenbleiben

Edit wenns A —> ED|A wäre könntest du das A natürlich, weglassen weil es auf sich selber abbildet, das ist bei A –> AA aber gerade nicht der Fall