Word problem

from Wikipedia, the free encyclopedia

In theoretical computer science, the word problem of a formal language is the decision problem to determine whether a given word belongs to the language or not. The word problem of a language is decidable if its characteristic function can be calculated , which is defined by

So language has a decidable word problem if there is an algorithm that finds out in finite time whether or not. Every decision problem can be coded as a word problem in a formal language.

The difficulty of the word problem depends on the underlying class of languages. For the Chomsky hierarchy it is known:

  • The word problem for type 0 languages ​​is recursively enumerable and not decidable.
  • The word problem for type 1 languages ​​is decidable. The time required is exponential at most, the space complexity is exactly linear. This means that the word problem in particular can also be decided for further restricted language classes.
  • The word problem for type 2 languages ​​can be solved using the Cocke-Younger-Kasami algorithm (requires Chomsky normal form ) or the Earley algorithm (requires epsilon- free grammar). The time required is at most cubic, the space complexity is at most square.
  • The word problem for type 3 languages ​​can be solved by deterministic finite automata . The time complexity of the problem is linear, the space complexity is constant.

See also

Web links

Wiktionary: word problem  - explanations of meanings, word origins, synonyms, translations

Individual evidence

  1. Uwe Schöning : Theoretical Computer Science - in short . 5th edition. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1 , p. 13 .