Eindeutigkeit

Id: eindeut.tex,v 1.2 2006-10-23 22:28:20 waldmann Exp

Def: G heißt eindeutig, falls $ \forall$w $ \in$ L(G) genau ein Ableitungsbaum (T, m) existiert.

Bsp: ist {S$ \to$aSb| SS|$ \epsilon$} eindeutig?

(beachte: mehrere Ableitungen S$ \to_{R}^{*}$w sind erlaubt, und wg. Kontextfreiheit auch gar nicht zu vermeiden.)


Die naheliegende Grammatik für arith. Ausdr.

expr -> number | expr + expr | expr * expr
ist mehrdeutig (aus zwei Gründen!)

Auswege:



Johannes Waldmann 2009-01-22