# 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 {otherwise}} \ 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.