Leerheitsproblem

Als Leerheitsproblem einer formalen Sprache L 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.
Für ist das Leerheitsproblem nicht entscheidbar.

Siehe auch

• Entscheidbarkeit
• Wortproblem

Kategorie:Theoretische Informatik

See also: Leerheitsproblem, Chomsky-Hierarchie, Entscheidbarkeit, Formale Sprache, Theoretische Informatik, Wortproblem