Leerheitsproblem

Als Leerheitsproblem bezeichnet man in der theoretischen Informatik das Problem, zu entscheiden, ob eine in Form einer formalen Grammatik gegebene formale Sprache ${\displaystyle L}$ leer ist, also ${\displaystyle L=\emptyset }$, oder nicht. Das Problem ist also, herauszufinden, ob es Wörter gibt, die den Regeln der Grammatik genügen, oder nicht.

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.