Rekursive Inferenz

Einfache Sprache

Die Idee der Rekursiven Inferenz ist, Wörter zu nehmen von denen man weiß, dass sie in der Sprache der jeweiligen Variable des Bodys (rechte Seite der Produktionsregel) sind, und diese mit Terminalsymbolen so zu konkatenieren wie es die Produktionsregel vorschreibt. Daraus folgt das die durch die Konkatenation entstanden Zeichenkette in der Sprache der Head (linke Seite der Produktionsregel) Variable ist.

Def. Rekursive Inferenz

Beispiel

Gegeben die Kontextfreie Grammatik $\mathcal G$ definiert durch die Produktionsregeln $E\to I\;|\; E+E\;|\;E*E\;|\;(E)$ und $I\to a\;|\;b\;|\; I0\;|\;I1\;|\;\varepsilon$. Dann ergibt sich folgende Rekursive Inferenz, hier in form eine Tabelle dargestellt:

Step	Inferierte Zeichenkette	in Sprache	Produktionsregel	benutze Zeichenketten
1	a	I	I -> a
2	b	I	I -> b
3	b0	I	I -> I0	2
4	b00	I	I -> I0	3
5	a	E	E -> I	1
6	b00	E	E -> I	4
7	a+b00	E	E -> E + E	5,6
8	(a+b00)	E	E -> (E)	7
9	a*(a+b00)	E	E -> E * E	5,8