Recursively enumerable language
In
Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable.
The class of all recursively enumerable languages is called RE.
Definitions
There are three equivalent definitions of a recursively enumerable language:
- A recursively enumerable language is a alphabet of the language.
- A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) which will enumerate all valid strings of the language. Note that if the language is infinite, the enumerating algorithm provided can be chosen so that it avoids repetitions, since we can test whether the string produced for number n is "already" produced for a number which is less than n. If it already is produced, use the output for input n+1 instead (recursively), but again, test whether it is "new".
- A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any string in the language as input but may either halt and reject or loop forever when presented with a string not in the language. Contrast this to recursive languages, which require that the Turing machine halts in all cases.
All regular, context-free, context-sensitive and recursive languages are recursively enumerable.
Example
The set of
Some other recursively enumerable languages that are not recursive include:
Closure properties
Recursively enumerable languages (REL) are closed under the following operations. That is, if L and P are two recursively enumerable languages, then the following languages are recursively enumerable as well:
- the Kleene star of L
- the concatenation of L and P
- the union
- the intersection .
Recursively enumerable languages are not closed under
See also
Sources
- Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
- Kozen, D.C. (1997), Automata and Computability, Springer.
External links
- Complexity Zoo: Class RE
- Lecture slides