Recursive Language Article Index for
Recursive 		Website Links For
Language 		 

Information About

Recursive Language
  CATEGORIES ABOUT RECURSIVE LANGUAGE
   
recursion theory
   
formal languages
   
theory of computation
   
SHOPPER'S DELIGHT
 
Shop For:  
Department
Price Minimum:
Price Maximum:
      



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.


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''--- of ''L''

  • the non-erasing Homomorphism φ(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.


REFERENCES


  • 1 Chapter 4: Decidability, pp.151–170.



EXTERNAL LINKS