boolean isElemP(X,Y \in t[i,j],Z \in t[l,m]) {
	/**
	 	Prüft, ob eine sich aus X, einem Y aus t[i,j] und einem Z aus
		t[l,m] eine Produktionsregel X->XZ der gegebenen Grammatik er-
		zeugen lässt.
		Die Funktion terminiert und gibt "true" zurück, sobald eine
		Regel gefunden wurde.
		Lässt sich aus allen möglichen Kombinationen keine passende
		Regel erzeugen, so gibt die Funktion "false" zurück.
	**/
}

void derive2Terminal(X \in I) {
	/**
		Leitet ein Nichtterminal zu einem Terminal ab, wenn eine ent-
		sprechende Produkionsregel in P existiert. Wenn keine existiert,
		liegt ein Fehler in der Recognitionmatrix vor.
	**/
}

addKnode(X) {
	/**
		Fügt dem Baum einen Knoten mit der Markierung X hinzu
	**/
}

void rek(t[i,j],A) {

	k:=1;
	found=false;

	if (j==1) then {
		addKnode(derive2Terminal(A));
		return;
	} // END OF IF
	else {

		while(!found) do {
			if isElemP(A,B \in t[i,k],C \in t[i+k,j-k]) then {
				found:=true;
				addKnode(B); 		// füge eine Knoten für den Unterbaum, der mit B beginnt hinzu
				addKnode(C);		// füge eine Knoten für den Unterbaum, der mit C beginnt hinzu
				rek(t[i,k],B);		// rufe die Funktion rekursiv für den Unterbaum B auf
				rek(t[i+k,j-k],C);	// rufe die Funktion rekursiv für den Unterbaum C auf
			} // END OF IF
			else {
				k++; // wenn keine Produktionsregel gefunden wurde, wird das nächste Paar von Einträgen aus der Matrix gewählt.
			} // END OF ELSE
		} // END OF WHILE
	} //END OF ELSE

}

r(tau):=S

rek(t[1,n],S);