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 ${\displaystyle L}$ ${\displaystyle \chi _{L}}$

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

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. ${\displaystyle L}$ ${\displaystyle w\in L}$

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

• Equivalence problem
• Finiteness problem
• Emptiness problem
• Optimization problem
• Search problem

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 .