Reduzierte Grammatiken

Def: Die Grammatik G heißt reduziert,

wenn alle Variablen erreichbar und produktiv sind.

Satz: zu jeder CFG G gibt es eine reduzierte CGF G' mit L(G) = L(G').

Beweis: lösche in G zuerst alle nicht produktiven Variablen,

dann alle (im Rest) nicht erreichbaren Variablen

(jeweils mit allen Regeln, in denen sie vorkommen)

Aufgabe: warum gerade diese Reihenfolge?



Johannes Waldmann 2006-02-02