Endlichkeitsproblem

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


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Chain Code Pictures — Ketten Kode Bilder (Chain Code Pictures) sind Bilder, die in erster Linie mit Hilfe von formalen Grammatiken erzeugt werden. Die von solchen Grammatiken generierten Wörter werden hierbei jeweils als genau ein Bild interpretiert, indem die… …   Deutsch Wikipedia

  • Chomsky-Hierarchie — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der Theoretischen Informatik. Sie ist eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Entscheidbare Menge — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Entscheidbarkeit — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Entscheidungsproblem — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Ketten-Code-Bilder — Ketten Kode Bilder (Chain Code Pictures) sind Bilder, die in erster Linie mit Hilfe von formalen Grammatiken erzeugt werden. Die von solchen Grammatiken generierten Wörter werden hierbei jeweils als genau ein Bild interpretiert, indem die… …   Deutsch Wikipedia

  • Ketten-Kode-Bilder — (Chain Code Pictures) sind Bilder, die in erster Linie mit Hilfe von formalen Grammatiken erzeugt werden. Die von solchen Grammatiken generierten Wörter werden hierbei jeweils als genau ein Bild interpretiert, indem die einzelnen Buchstaben als… …   Deutsch Wikipedia

  • Kontextfrei — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: OMA Verständlichkeit bei den Beispielen ausbauen Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst. Als Kontextfreie Sprache ( …   Deutsch Wikipedia

  • Kreativproblem — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Rekursiv entscheidbar — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”