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.

Examples

• 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.

Solution

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. Efficient algorithms are the CYK algorithm and Earley's 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.

See also: word problem for groups.