Added to Favorites

Popular Searches

Definitions

Nearby Words

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.
## Word problem

## Examples

## Solution

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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday July 12, 2007 at 14:07:54 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday July 12, 2007 at 14:07:54 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.