Recursive Language

In mathematical logic and computer science, a recursive language — a type of formal language, also called decidable, or Turing-decidable. The class of all recursive languages is often denoted by R, although the same notation is also used for the class RP.

This type of language is not defined within the Chomsky hierarchy (Chomsky 1959).

Definitions

Two equivalent definitions of a recursive language are used:

1. A formal recursive language — a recursive subset of the set of all possible words over the alphabet of the formal language.
2. A recursive language — a formal language for which there exists a Turing machine that halts on any input string and accepts it if and only if it belongs to the language. Such a machine is said to be a decider that decides the given recursive language.

All recursive languages are also recursively enumerable. All regular, context-free, and context-sensitive languages are recursive.

Closure properties

Recursive languages are closed under the operations listed below. Thus, if L and P are recursive languages, the following languages are also recursive:

• Kleene closure ;
• homomorphic image , where — is a homomorphism such that , where — is the empty string;
• concatenation ;
• union ;
• intersection ;
• complement ;
• difference .