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:

1. A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.
2. 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

Recursivel 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

Note that recursive languages are not closed under set difference. The set difference L\P may or may not be recursive.