Wortproblem

Wortproblem

Als Wortproblem einer formalen Sprache bezeichnet man in der Theoretischen Informatik das Entscheidungsproblem, zu einem gegebenen Wort festzustellen, ob dieses zur Sprache gehört oder nicht. Das Wortproblem einer Sprache L ist entscheidbar, wenn ihre charakteristische Funktion χL berechenbar ist. Sie ist definiert durch

\chi_L\colon \Sigma^\ast \to \{0,1\};\ w \mapsto
\begin{cases}
   1, & \text{falls } w \in L \\
   0, & \text{sonst}
\end{cases}

Die Sprache L hat also ein entscheidbares Wortproblem, wenn es einen Algorithmus gibt, der in endlicher Zeit herausfindet, ob w \in L oder nicht. Jedes Entscheidungsproblem lässt sich als Wortproblem einer formalen Sprache codieren.

Die Schwierigkeit des Wortproblems hängt von der zugrunde gelegten Klasse der Sprachen ab. Für die Chomsky-Hierarchie ist bekannt:

  • Das Wortproblem für Typ-1-Sprachen ist entscheidbar. Der Zeitbedarf ist höchstens exponentiell, die Platzkomplexität ist exakt linear. Damit ist insbesondere das Wortproblem für weiter eingeschränkte Sprachklassen auch entscheidbar.
  • Das Wortproblem für Typ-3-Sprachen ist durch deterministische endliche Automaten lösbar. Die Zeitkomplexität des Problems ist linear, die Platzkomplexität ist konstant.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

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

  • Termersetzung — Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik. Sie bilden insbesondere die Grundlage der Logik und funktionalen Programmierung. Ferner spielen sie eine wichtige Rolle beim Wortproblem und bei… …   Deutsch Wikipedia

  • Termersetzungsregel — Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik. Sie bilden insbesondere die Grundlage der Logik und funktionalen Programmierung. Ferner spielen sie eine wichtige Rolle beim Wortproblem und bei… …   Deutsch Wikipedia

  • Präsentation einer Gruppe — In der Mathematik ist die Präsentation einer Gruppe gegeben durch eine Liste von Elementen, die die Gruppe erzeugen, und eine Liste von Relationen, die zwischen diesen Erzeugern bestehen. Zum Beispiel wird die zyklische Gruppe der Ordnung n… …   Deutsch Wikipedia

  • Termersetzungssystem — Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik. Sie bilden insbesondere die Grundlage der Logik und funktionalen Programmierung. Ferner spielen sie eine wichtige Rolle beim Wortproblem und bei… …   Deutsch Wikipedia

  • Reduktionssystem — In der Mathematischen Logik und der Theoretischen Informatik steht die Bezeichnung Reduktionssystem, oder abstraktes Reduktionssystem, abgekürzt ARS, für eine Verallgemeinerung von Termersetzungssystemen. In seiner einfachsten Form ist ein ARS… …   Deutsch Wikipedia

  • Freie Gruppe — In der Mathematik heißt eine Gruppe frei, wenn sie eine Teilmenge S enthält, so dass jedes Gruppenelement auf genau eine Weise als (reduziertes) Wort von Elementen in S und deren Inversen geschrieben werden kann. Hierbei ist die Reihenfolge der… …   Deutsch Wikipedia

  • Kontextfreie Grammatik — In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik eine Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminal auf eine beliebig lange Folge von Nichtterminalen und Terminale abgeleitet wird …   Deutsch Wikipedia

  • NP-Vollständig — Der Begriff NP Vollständigkeit ist ein Begriff aus der Komplexitätstheorie der Theoretischen Informatik, der im Jahre 1971 von Stephen A. Cook durch den Satz von Cook eingeführt wurde. Er zeichnet spezielle formale Sprachen der Komplexitätsklasse …   Deutsch Wikipedia

  • NP-vollständig — Der Begriff NP Vollständigkeit ist ein Begriff aus der Komplexitätstheorie der Theoretischen Informatik, der im Jahre 1971 von Stephen A. Cook durch den Satz von Cook eingeführt wurde. Er zeichnet spezielle formale Sprachen der Komplexitätsklasse …   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

Share the article and excerpts

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