Recursive language

From Wikipedia, the free encyclopedia

A recursive language in mathematics, logic and computer science, is a type of formal language which is also called recursive, decidable or Turing-decidable. The class of all recursive languages is often called R, although this name is also used for the class RP.

This type of language was not defined in the Chomsky hierarchy of (Chomsky 1959).

Contents 1 Definitions 2 Closure properties 3 References 4 See also 5 External links

[edit] 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.

[edit] Closure 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 ^*
• the image φ(L) under a e-free homomorphism φ
• the concatenation
• the union
• the intersection
• 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.

[edit] References

• Michael Sipser (1997). "Decidability", Introduction to the Theory of Computation. PWS Publishing, 151–170. ISBN 0-534-94728-X. 
• Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control 2 (2): 137–167. 

[edit] See also

• Recursively enumerable language
• Recursion
• Recursive acronym

[edit] External links

Automata theory: formal languages and formal grammars

Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
n/a	Indexed	Indexed	Nested stack
n/a	Tree-adjoining etc.	(Mildly context-sensitive)	Embedded pushdown
Type-2	Context-free	Context-free	Nondeterministic pushdown
n/a	Deterministic context-free	Deterministic context-free	Deterministic pushdown
Type-3	Regular	Regular	Finite
n/a		Star-free	Counter-Free
Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it.