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 property follows from the fact that the set difference can be expressed in terms of intersection and complement.
| Automata theory: formal languages and formal grammars | |||
|---|---|---|---|
| Chomsky hierarchy | Grammars | Languages | Minimal automaton |
| Type-0 | Unrestricted | Recursively enumerable | Turing machine |
| Unrestricted | Recursive | Turing machine | |
| Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
| Type-2 | Context-free | Context-free | Pushdown |
| Type-3 | Regular | Regular | Finite |
| Each category of languages or grammars is a proper superset of the category directly beneath it. | |||