Recursive language

Recursive language

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 Turing machine which always halts when given a finite sequence of symbols from the alphabet of the language as input and which accepts exactly those words from the alphabet of the language that are part of the language and rejects all other words. Recursive languages are 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). All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.

Contents

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 finite 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.

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.

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 an 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

  • 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. 

See also


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Recursive — may refer to:*Recursion *Recursively enumerable language *Recursively enumerable set *Recursive filter *Recursive function *Recursive language *Recursive acronym *Recursive set *Primitive recursive function …   Wikipedia

  • Recursive languages and sets — This article is a temporary experiment to see whether it is feasible and desirable to merge the articles Recursive set, Recursive language, Decidable language, Decidable problem and Undecidable problem. Input on how best to do this is very much… …   Wikipedia

  • Recursive set — In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set. A more… …   Wikipedia

  • Language identification in the limit — is a formal model for inductive inference. It was introduced by E. Mark Gold in his paper with the same title [http://www.isrl.uiuc.edu/ amag/langev/paper/gold67limit.html] . In this model, a learner is provided with presentation of some language …   Wikipedia

  • Recursive function — may refer to: Recursion (computer science), a procedure or subroutine, implemented in a programming language, whose implementation references itself A total computable function, a function which is defined for all possible inputs See also μ… …   Wikipedia

  • Recursive acronym — A recursive acronym (synonymous with metacronym,[1] recursive initialism, and recursive backronym) is an acronym or initialism that refers to itself in the expression for which it stands. The term was first used in print in April 1986.[2]… …   Wikipedia

  • Recursive definition — A recursive definition or inductive definition is one that defines something in terms of itself (that is, recursively), albeit in a useful way. For it to work, the definition in any given case must be well founded, avoiding an infinite regress.… …   Wikipedia

  • Recursive type — In computer programming languages, a recursive type is a data type for values that may contain other values of the same type.An example is the list type, in Haskell: data List a = Nil | Cons a (List a) This indicates that a list of a s is either… …   Wikipedia

  • Recursive transition network — A recursive transition network ( RTN ) is a graph theoretical schematic used to represent the rules of a context free grammar. RTNs have application to programming languages, natural language and lexical analysis. Any sentence that is constructed …   Wikipedia

  • Recursively enumerable language — In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing acceptable. It is known as a type 0 language in the Chomsky hierarchy of formal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”