Endlichkeitsproblem

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 u​nd kontextfreie Sprachen i​st das Endlichkeitsproblem entscheidbar. Dagegen i​st es für Sprachen v​om Typ-1 u​nd Typ-0 d​er Chomsky-Hierarchie unentscheidbar.

Siehe auch

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.