Die Entscheidbarkeit des Leerheitsproblems hängt von der Komplexität der zugrundeliegenden Grammatik ab: Für die Grammatiken vom Typ 2 oder höher in der Chomsky-Hierarchie ist das Leerheitsproblem entscheidbar, für die Grammatiken bis Typ 1 im Allgemeinen jedoch nicht. Gesucht ist ein Algorithmus zur Lösung des Leerheitsproblems. Der Ansatz ...