Endlichkeitsproblem

Als Endlichkeitsproblem einer formalen Sprache $L$ bezeichnet man in der theoretischen Informatik das Problem, zu entscheiden, ob die Sprache endlich ist. Eine formale Sprache wird als endlich bezeichnet, wenn die Menge ihrer „Wörter“ endlich ist, man schreibt dann auch $\left|L\right|<\infty$.

Für reguläre und kontextfreie Sprachen ist das Endlichkeitsproblem entscheidbar. Dagegen ist es für Sprachen vom Typ-1 und Typ-0 der Chomsky-Hierarchie unentscheidbar.

Siehe auch

• Äquivalenzproblem
• Optimierungsproblem
• Schnittproblem
• Wortproblem