Word problem (computability)

In computability theory, the word problem is a decision problem concerning formal languages. The problem is to construct an algorithm to decide for a given word if it belongs to a formal language or not.

[edit] Word problem

Given a formal language L generated by a formal grammar G := (N, Σ, P, S), is there an algorithm to decide for some given w in Σ* if w is in L or not.

The strings over {a, b} that consist of alternating a's and b's.
The strings over {a, b} that contain an equal amount of a's and b's.
The strings that describe a graph with edges labeled with natural numbers indicating their length, two vertices of the graph, and a path in the graph which is the shortest path between the two vertices.
The strings that describe a set of integers such that a subset of them has the sum 0.

Using the Chomsky hierarchy for formal grammars we can give the following answer to the word problem.

Type-3 Grammar:

The word problem for regular languages is decidable. The complexity for the algorithm is linear.

Type-2 Grammar:

For context-free languages the word problem is decidable. An efficient algorithm is the CYK algorithm, assuming the grammar is given in the Chomsky normal form.

Type-1 Grammar

For context-sensitive languages the word problem is decidable. The complexity for the algorithm is exponential.

Type-0 Grammar

For recursively enumerable languages the word problem is undecidable.