In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language. Equivalently, a formal language is recursive if there exists a total Turing machine (a Turing machine that halts for every given input) that, when given a finite sequence of symbols from the alphabet of the language as input (any string containing only characters in the language's alphabet) accepts only those that are part of the language and rejects all other strings. Recursive languages are also called decidable.
The concept of decidability may be extended to other models of computation. For example one may speak of languages decidable on a non-deterministic Turing machine. Therefore, whenever an ambiguity is possible, the synonym for "recursive language" used is Turing-decidable language, rather than simply decidable.
This type of language was not defined in the Chomsky hierarchy of (Chomsky 1959). All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.
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 that, when presented with any finite input string, halts and accept if the string is in the language, and halts and rejects otherwise. The Turing machine always halts: it is known as a decider and is said to decide the recursive language.
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
- The image φ(L) under an e-free homomorphism φ
- The concatenation
- The union
- The intersection
- The complement of
- The set difference
The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.
- Michael Sipser (1997). "Decidability". Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 0-534-94728-X
- Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.