|
In mathematics, logic and computer science, a formal language is called recursively enumerable, partially decidable or Turing-recognizable if there exists an algorithm to enumerate all valid strings of the language.
Alternatively we can define them as those languages for which an algorithm exists, that when given string w as input, halts and outputs YES if and only if w belongs to the language L. If w does not belong to the language L, the algorithm either runs forever, or halts and outputs NO. If the algorithm always halts the language is called recursive.
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".
All regular, context-free, context-sensitive and recursive languages are recursively enumerable.
Definition
A formal language is called recursively enumerable if and only if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language.
Properties
If L and P are two recursively enumerable languages, then the following languages are recursively enumerable as well:
- the Kleene star L* of L
- the concatentation LP of L and P
- the union L∪P
- the intersection L∩P
Note that the set difference L\P and in particular the complement of L need not be recursively enumerable.
| 
