In computability theory, the word problem is a decision problem concerning formal languages. The problem is to construct an algorithm to decide for a given word if it belongs to a formal language or not.

PropertyValue
dbpprop:abstract
  • In computability theory, the word problem is a decision problem concerning formal languages. The problem is to construct an algorithm to decide for a given word if it belongs to a formal language or not.
  • 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 <math>L ist entscheidbar, wenn ihre charakteristische Funktion <math>\chi_L berechenbar ist. Sie ist definiert durch <math>\chi_L:\; \Sigma^\ast \to \{0,1\};\ w \mapsto \begin{cases} 1, & \text{falls } w \in L \\ 0, & \text{sonst} \end{cases} Die Sprache <math>L hat also ein entscheidbares Wortproblem, wenn es einen Algorithmus gibt, der in endlicher Zeit herausfindet, ob <math>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-0-Sprachen ist rekursiv aufzählbar und nicht entscheidbar. 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-2-Sprachen ist durch den Cocke-Younger-Kasami-Algorithmus lösbar, der Chomsky-Normalform voraussetzt. Der Zeitbedarf ist höchstens kubisch, die Platzkomplexität ist höchstens quadratisch. 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.
dbpprop:hasPhotoCollection
rdfs:comment
  • In computability theory, the word problem is a decision problem concerning formal languages. The problem is to construct an algorithm to decide for a given word if it belongs to a formal language or not.
  • 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 <math>L ist entscheidbar, wenn ihre charakteristische Funktion <math>\chi_L berechenbar ist.
rdfs:label
  • Word problem (computability)
  • Wortproblem
owl:sameAs
skos:subject
foaf:page