Recursive language
A recursive language in mathematics, logic and computer science, is a type of formal language which is also called recursive, decidable or Turing-decidable. This type of language is conspicuously missing from the Chomsky hierarchy.
Definitions
There are two equivalent major definitions for the concept of a recursive language:
- A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.
- A recursive language is a formal language for which there exists a turing machine which will, when presented with any input string, halt and accept if the string is in the language, and halt and reject otherwise. The turing machine always halts; it is known as a decider and is said to decide the recursive language.
All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.
Properties
Recursive languages are closed under the following operations. That is, if L and P are two recursive languages, then the following languages are recursive as well:
- the Kleene star L* of L
- the concatenation LP of L and P
- the union L∪P
- the intersection L∩P
- the complement of L
- the set difference L\P
The last propery follows from the fact that the set difference can be expressed in terms of intersection and complement.