Word problem (computability)

As word problem of a formal language is defined in theoretical computer science the decision problem to determine for a given word, whether this belongs to the language or not. The word problem of a language is decidable if its characteristic function is computable. It is defined by

The language also has a decidable word problem if there is an algorithm that finds in a finite time, whether or not. Each decision problem can be encoded as a word problem of a formal language.

The difficulty of the word problem depends on the underlying class of languages. For the Chomsky hierarchy 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 at most exponentially, the space complexity is exactly linear. Thus, in particular, the word problem for further restricted language classes is also decidable.

• The word problem for type 2 languages ​​is solvable by the Cocke - Younger - Kasami algorithm, which requires the Chomsky normal form. The time required is at most cubic, the space complexity is at most quadratic.

• The word problem for type-3 languages ​​is solvable by deterministic finite automata. The time complexity of the problem is linear, the space complexity is constant.