Endlichkeitsproblem

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 15. Dezember 2018 um 12:36 Uhr durch imported>Sokonbud(916404) (→‎Siehe auch: schon im Artikel mit Wikilink und form).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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

Abgerufen von „https://de.wikiup.org/index.php?title=Endlichkeitsproblem&oldid=183725301“