Satz Syntaxbaum, erweiterte Ableitung und rekursive Inferenz sind äquivalent

Einfache Sprache

Def. Satz Syntaxbaum, erweiterte Ableitung und rekursive Inferenz sind äquivalent

Sei $\mathcal G = (T,V,S,P)$ eine Kontextfreie Grammatik, $w\in T^*$ und $A\in V$. Dann sind folgende Aussagen äquivalent:

1. Rekursive Inferenz zeigt, dass $w$ in der Sprache von $A$ ist.
2. $A\overset{*}\Rightarrow w$,
3. $A\overset{*}{\underset{lm}\Rightarrow} w$
4. $A\overset{*}{\underset{rm}\Rightarrow} w$
5. Es existiert ein Syntaxbaum mit Wurzel $A$ und yield $w$.

Beweisidee: Wir machen Ringschluss über in folgender Reihenfolge 1. -> 5. -> 3. -> 2. -> 1.. Von 3. zu 2. is offensichtlich, da jede leftmost erweiterte Ableitung auch eine “einfache” erweiterte Ableitung ist.

Beweis: Der Beweis durch Ringschluss mit folgenden Lemmas:

• Satz von rekursiver Inferenz zu Syntaxbaum
• Satz von Syntaxbaum zu erweiterte Ableitung
• Satz von erweiterte Ableitung zu rekursiver Inferenz