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).
There are two equivalent major definitions for the concept of a recursive language:
All recursive languages are also ...
more
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).
There are two equivalent major definitions for the concept of a recursive language:
All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.
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 last property follows from the fact that the set difference can be expressed in terms of intersection and complement.
less
