Word problem (computability)
- 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.
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.
olution
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.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown … Wikipedia
Problem — A problem is an obstacle which makes it difficult to achieve a desired goal, objective or purpose. It refers to a situation, condition, or issue that is yet unresolved. In a broad sense, a problem exists when an individual becomes aware of a… … Wikipedia
Undecidable problem — In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct an algorithm that leads to a yes or no answer the problem is not decidable.A decision problem is any … Wikipedia
Decision problem — A decision problem has only two possible outputs, yes or no (or alternately 1 or 0) on any input. In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes or no answer,… … Wikipedia
List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… … Wikipedia
Halting problem — In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever. This is equivalent to the problem of deciding, given a… … Wikipedia
List of mathematics articles (W) — NOTOC Wad Wadge hierarchy Wagstaff prime Wald test Wald Wolfowitz runs test Wald s equation Waldhausen category Wall Sun Sun prime Wallenius noncentral hypergeometric distribution Wallis product Wallman compactification Wallpaper group Walrasian… … Wikipedia
Combinatorics on words — Construction of a Thue Morse infinite word Combinatorics on words is a branch of mathematics which applies combinatorics to words and formal languages. The study of combinatorics on words arose independently within several branches of mathematics … Wikipedia
Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… … Wikipedia
Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… … Wikipedia
