FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

Greibach Normalform

Greibach Normalform 2006-07-15 22:49
Anonymer User
Eine KFG ist in Greibach Normalform, gdw.
[img]http://mokrates.de/cgi-bin/texstring?P%20%5Csubseteq%20V%20%5Ctimes%20%5CSigma%20%5Ccdot%20V%5E*[/img]

Was genau bedeutet das? Also wofür steht dort
[img]http://mokrates.de/cgi-bin/texstring?%5Ctimes[/img] und
[img]http://mokrates.de/cgi-bin/texstring?%5Ccdot[/img] ?

Re: Greibach Normalform 2006-07-15 23:08
f0k
x ist das, was wir sonst als Pfeil darstellen (denn eine Produktion ist eigentlich ein Tupel, die Darstellung mit Pfeil ist nur eine andere Schreibweise, die wir dafür eingeführt haben - und die Menge aller Tupel mit Elementen eines bestimmten Typs erhält man über das Komplexprodukt x (N x M bezeichnet z.B. alle Tupel (x, y) mit x aus N und y aus M)).

Der Malpunkt ist die Konkatenation, d.h. das simple Hintereinanderschreiben von Zeichen.


Die Greibach-Normalform erlaubt also nur Produktionen, bei denen auf der linken Seite ein einzelnes Nonterminal steht (klar, das muss bei allen KFGs so sein) und auf der rechten Seite erst ein Terminal und dann eine beliebige Anzahl an Nonterminalen (möglicherweise auch gar keins).

Re: Greibach Normalform 2006-07-15 23:15
Anonymer User
Super, danke - das erklärt einiges :)