Recursive language

related topics
{math, number, function}
{language, word, form}

A recursive language in mathematics, logic and computer science is a type of formal language which is also called 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

Definitions

There are two equivalent major definitions for the concept of a recursive language:

By the second definition, any decision problem can be shown to be decidable by exhibiting an algorithm for it that terminates on all inputs. An undecidable problem is a problem that is not decidable.

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 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 L \circ P
  • the union L \cup P
  • the intersection L \cap P
  • the complement of L
  • the set difference LP

The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.

References

Full article ▸

related documents
Greibach normal form
Lazy initialization
Direct sum of groups
Essential singularity
Derivative of a constant
Context-sensitive language
Galois group
Sigmoid function
Disjoint sets
Identity function
Chart parser
Sedenion
Markov process
Endomorphism ring
Hilbert's Nullstellensatz
Harmonic analysis
Rectangle
Constant folding
Ring homomorphism
Co-NP
Water, gas, and electricity
Linearity of integration
Sieve of Eratosthenes
Context-free language
Distinct
Z notation
Euclidean distance
Lint (software)
List of Fourier-related transforms
Discrete mathematics