Wikipedia · einfach zusammengefasst · Stand
Endlichkeitsproblem
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 …
Endlichkeitsproblem formaler Sprachen
Das Endlichkeitsproblem ist die Frage, ob eine formale Sprache L endlich ist. Eine formale Sprache besteht aus einer Menge von Wörtern. Sie heißt endlich, wenn diese Wortmenge endlich viele Elemente enthält; dafür schreibt man |L| < ∞.
Für reguläre Sprachen und kontextfreie Sprachen ist das Endlichkeitsproblem entscheidbar. Das bedeutet, dass es ein Verfahren gibt, mit dem man für jede solche Sprache in endlicher Zeit feststellen kann, ob sie endlich ist.
Für Sprachen vom Typ 1 und Typ 0 der Chomsky-Hierarchie ist das Endlichkeitsproblem dagegen unentscheidbar. Für diese Sprachklassen gibt es somit kein allgemeines Verfahren, das für jede Sprache zuverlässig entscheidet, ob sie endlich ist.
