Recursive language: Difference between revisions

Revision as of 12:16, 2 May 2013

Revision as of 12:16, 2 May 2013

Line 1:

{{About|a class of formal languages as they are studied in mathematics and theoretical computer science. Recursive languages are also called '''decidable'''.|computer languages that allow a function to call itself recursively |Recursion (computer science)}}.

In [[mathematics]], [[logic]] and [[computer science]], a [[formal language]] (a [[set (mathematics)|set]] of finite sequences of [[symbol (formal)|symbol]]s taken from a fixed [[alphabet (computer science)|alphabet]]) is called '''recursive''' if it is a [[recursive set|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 [[total Turing machine]] (a [[Turing machine]] which halts for every given input) which when given a finite sequence of symbols w from the alphabet of the language as input (any string containing only characters in the language's alphabet) accepts only those w which are part of the language and rejects all other strings.