Als Endlichkeitsproblem einer formalen Sprache 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 .
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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.