Wortproblem:

Problem: Member
Eingabe: Grammatik G und Wort w
Frage: Gilt w ist element von L(G)?
Satz
Es gibt einen Algorithmus, der das Wortproblem für Typ1-Grammatiken löst
Beweis
Seien m,neN,dann defnieren wir die Mengen Tn/m wie folgt: