Eindeutigkeit

Id: eindeut.tex,v 1.1 2011-10-11 18:13:54 waldmann Exp

Def: G heißt eindeutig, falls ∀w∈L(G) genau ein Ableitungsbaum (T, m) existiert.

Bsp: ist {S→aSb| SS| ε} eindeutig?

(beachte: mehrere Ableitungen S→_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 2012-10-10