chomsky versus greibach

elise

In der Theoretischen Informatik versteht man unter einer Normalform meist eine einfache Form einer kontextfreien Grammatik.

zur chomsky normalform finde ich:
Für jede kontextfreie Grammatik G existiert eine äquivalente Grammatik G' in Chomsky-Normalform,
Das sei eine starke Einschränkung für die kontextfreie Grammatik: Ableitungsbäume für solche Grammatiken sind-bis auf den letzten Ableitungsschritt- Binärbäume.

zu greibach:
zu jeder kontextfreien Grammatik G gibt es eine Greibach Normalform Grammatik G'

darüber hinaus:
Die Greibach Normalform isteine natürliche Erweiterung der regulären Grammatik, dort wäre nur der Fall k=0 und k=1 zugelasssen.

und: für die Herrstellung der Greibach Normalform soll man von der Chomsky Grammatik ausgehen

dazu noch diesen satz:
Die Greibach-Normalform hat den Vorteil, dass bei jedem Ableitungsschritt jeweils genau ein Terminalzeichen entsteht.

meine frage: ich verstehe den genannten "Vorteil" nicht, vielleicht, weil mir die ganze Sache noch etwas abstrakt bleibt.
Welchen Vorteil hat die Greibach gegenüber der Chomsky normalform?

thanks

edit: chomsky berichtigt

TGGC

So wie ich das verstehe, brauchst du bei Greibach nicht so viele Schritte/Regeln, wie bei Chomsky, weil du z.b. aus den Regeln N1 -> N2N3;N2 -> T1 einfach N1->T1N3 machst (T für terminlae, N nichterminale). Für x Terminale braucht Greibach x Schritte, Chomsky 2x.

Chomsky, ohne r, Chomsky, merkst euch das mal, Chomsky heisst das, CHOMSKY, es ist zum verzweifeln...

Bye, TGGC (Pipe my World.)

elise

thanks for antwort.

aber das "euch" kannste dir sparen, ich hab ihn falsch geschrieben, bin schon von anderer seite drauf hingewiesen worden.
also beruhige dich, TGGGC.

TGGC

Darum

Bye, TGGC (Pipe my World.)

elise