Word problem
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
- ↑ Uwe Schöning : Theoretical Computer Science - in short . 5th edition. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1 , p. 13 .