Leerheitsproblem

Als Leerheitsproblem einer formalen Sprache bezeichnet man in der Theoretischen Informatik das Problem, zu entscheiden, ob die Sprache leer ist, also , oder nicht.

Für (vgl. Chomsky-Hierarchie) ist das Leerheitsproblem entscheidbar.

Siehe auch