Satz Größe eines Syntaxbaum

Einfache Sprache

Def. Satz Größe eines Syntaxbaum

Sei $G$ ein Syntaxbaum für eine KFG $\mathcal G = (T,V,S,P)$ in Chomsky-Normalform. Sei $w\in T^*$ der Ertrag von $G$. Wenn die Länge des längsten Kantenzugs $n$ ist, dann gilt $|w|\leq 2^{n-1}$.

Beweis: Induktion über $n$.

IA: Sei $n$ = 1. Da $\mathcal G$ in CNF (Chomsky-Normalform) ist, muss $G$ aus einer Wurzelknoten und einem Blattknoten bestehen. Der Ertrag $w$ ist dann die Beschriftung von dem Blattknoten, ein Terminalsymbol, und damit $|w| = 1$. Es gilt

IS: Sei $n>1$. Da $\mathcal G$ in CNF (Chomsky-Normalform) ist, muss die Wurzel $G$ ein Produktionsregel der Form $A\to BC$ darstellen. Da die Länge der Teilsyntaxbäume mit $B$ und $C$ als Wurzel nicht Größer als $n-1$ sein kann, haben sie nach IH ein Ertrag von maximal $2^{n-2}$. Der Ertrag von $G$ ist dann höchstens die Konkatenation der maximalen Erträge von $B$ und $C$, also $2^{n-2}+2^{n-2} = 2^{n-1}$.