Recursive language: Difference between revisions

Revision as of 23:07, 12 March 2015

Latest revision as of 08:12, 14 July 2025

(46 intermediate revisions by 28 users not shown)

Line 1:

{{Short description|Formal language in mathematics and computer science}}

{{About|a class of formal languages as they are studied in mathematics and theoretical computer science|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(or it''decidable'') language is a [[recursive set|recursive subset]] of the set[[Kleene closure]] of allan possible[[Alphabet finite sequences over the(formal languages)|alphabet of the language]]. Equivalently, a [[formal language]] is '''recursive''' if there exists a [[total Turing machine]] (athat [[Decider (Turing machine)|decides]] thatthe haltsformal forlanguage.{{sfnp|Sipser|2012}} everyIn given[[theoretical input)computer thatscience]], whensuch givenalways-halting aTuring finitemachines sequenceare ofcalled symbols[[total asTuring input,machine]]s accepts it if belongs to the language and rejects it otherwise. Recursive languages are also calledor '''decidablealgorithms'''.{{sfnp|Sipser|1997}}

The concept of '''decidability''' may be extended to other [[models of computation]]. For example, one may speak of languages decidable on a [[non-deterministic Turing machine]]. Therefore, whenever an ambiguity is possible, the synonym used for "recursive language" used is '''Turing-decidable language''', rather than simply ''decidable''.

The class of all recursive languages is often called '''[[R (complexity)|R]]''', although this name is also used for the class [[RP (complexity)|RP]].

This type of language was not defined in the [[Chomsky hierarchy]] of .{{Harvsfnp|Chomsky|1959}}. All recursive languages are also [[recursively enumerable language|recursively enumerable]]. All [[regular language|regular]], [[context-free language|context-free]] and [[context-sensitive language|context-sensitive]] languages are recursive.

== Definitions ==

Line 13 ⟶ 14:

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

# A recursive formal language is a [[recursive set|recursive]] [[subset]] inof the [[set (mathematics)|set]] of all possible words over thefinite-length [[alphabetformal language|words]] ofover thean [[alphabet (formal languagelanguages)|languagealphabet]].

# A recursive language is a [[formal language]] for which there exists a [[Turing machine]] that, when presented with any finite input [[literal string|string]], halts and accept if the string is in the language, and halts and rejects otherwise. Thedecider (Turing machine always halts: it is known as a [[Machine that always halts)|deciderdecides]] and is said to ''decide'' the recursive languageit.

ByOn the secondother definitionhand, anywe can show that a [[decision problem]] canis bedecidable shownby toexhibiting bea decidableTuring bymachine exhibitingrunning an [[algorithm]] for it that terminates on all inputs. An [[undecidable problem]] is a problem that is not decidable.

== Examples ==

As noted above, every context-sensitive language is recursive. Thus, a simple example of a recursive language is the set ''L={abc, {{not a typo|aabbcc}}, {{not a typo|aaabbbccc}}, ...}'';
more formally, the set

: <math>L=\{\,w \in \{a,b,c\}^* \mid w=a^nb^nc^n \mbox{ for some } n\ge 1 \,\}</math>
is context-sensitive and therefore recursive.

Examples of decidable languages that are not context-sensitive are more difficult to describe. For one such example, some familiarity with [[mathematical logic]] is required: [[Presburger arithmetic]] is the first-order theory of the natural numbers with addition (but without multiplication). While the set of [[First-order_logic#Formulas|well-formed formulas]] in Presburger arithmetic is context-free, every deterministic Turing machine accepting the set of true statements in Presburger arithmetic has a worst-case runtime of at least <math>2^{2^{cn}}</math>, for some constant ''c''>0 {{harv|Fischer|Rabin|1974}}, where ''n'' is the length of the given formula. Since every context-sensitive language can be accepted by a [[linear bounded automaton]], and such an automaton can be simulated by a deterministic Turing machine with worst-case running time at most <math>c^n</math> for some constant ''c'' {{citation needed}}, the set of valid formulas in Presburger arithmetic is not context-sensitive. On positive side, it is known that there is a deterministic Turing machine running in time at most triply exponential in ''n'' that decides the set of true formulas in Presburger arithmetic {{harv|Oppen|1978}}. Thus, this is an example of a language that is decidable but not context-sensitive.

Examples of decidable languages that are not context-sensitive are more difficult to describe. For one such example, some familiarity with [[mathematical logic]] is required: [[Presburger arithmetic]] is the first-order theory of the natural numbers with addition (but without multiplication). While the set of [[First-order_logic#Formulas|well-formed formulas]] in Presburger arithmetic is context-free, every deterministic Turing machine accepting the set of true statements in Presburger arithmetic has a worst-case runtime of at least <math>2^{2^{cnpn}}</math>, for some constant ''cp''>0 .{{harvsfnp|Fischer|Rabin|1974}} Here, where ''n'' isdenotes the length of the given formula. Since every context-sensitive language can be accepted by a [[linear bounded automaton]], and such an automaton can be simulated by a deterministic Turing machine with worst-case running time at most <math>cq^n</math> for some constant ''cq'' ,{{citation neededsfnp|Book|1974}}, the set of valid formulas in Presburger arithmetic is not context-sensitive. On a positive side, it is known that there is a deterministic Turing machine running in time at most triply exponential in ''n'' that decides the set of true formulas in Presburger arithmetic .{{harvsfnp|Oppen|1978}}. Thus, this is an example of a language that is decidable but not context-sensitive.

== Closure properties ==

Line 30 ⟶ 32:

Recursive languages are [[closure (mathematics)|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]] <math>L^*</math>

* The image φ(L) under an [[Homomorphism#Homomorphisms and e-free homomorphisms in formalFormal language theory|e-free homomorphism]] φ

* The concatenation <math>L \circ P</math>

* The union <math>L \cup P</math>

Line 41 ⟶ 43:

== See also ==

*[[Recursively enumerable language]]

*[[Computable set]]

*[[Recursion]]

== ReferencesNotes ==

{{reflist}}

* {{Cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | chapter = Decidability | pages = 151–170 | isbn = 0-534-94728-X|ref = harv|postscript = <!--None-->}}

* {{cite journal | last = Chomsky | first = Noam | year = 1959 | title = On certain formal properties of grammars | journal = Information and Control | volume = 2 | issue = 2 | pages = 137–167 | doi = 10.1016/S0019-9958(59)90362-6 | ref = harv}}

==References==

* {{cite journal | first1=Michael J. | last1=Fischer | authorlink1=Michael J. Fischer | first2=Michael O. | last2=Rabin | authorlink2=Michael O. Rabin | date=1974 | title=Super-Exponential Complexity of Presburger Arithmetic | url=http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps | journal=Proceedings of the SIAM-AMS Symposium in Applied Mathematics | volume=7 | pages=27–41 | ref=harv }}

*{{cite journal

*{{cite journal | last1 = Oppen | first1 = Derek C. | year = 1978 | title = A 2^{2^{2^''pn''}} Upper Bound on the Complexity of Presburger Arithmetic | url = http://www.sciencedirect.com/science/article/pii/0022000078900211/pdf?md5=0415089a2d692fcece18b43b5f63c67d&pid=1-s2.0-0022000078900211-main.pdf | format = PDF | journal = J. Comput. Syst. Sci. | volume = 16 | issue = 3| pages = 323–332 | doi = 10.1016/0022-0000(78)90021-1 }}

| last = Book | first = Ronald V. | author-link = Ronald V. Book

| doi = 10.1016/S0022-0000(74)80008-5

| journal = [[Journal of Computer and System Sciences]]

| mr = 366099

| pages = 213–229

| title = Comparing complexity classes

| volume = 9

| year = 1974}}

* {{cite journal | last = Chomsky | first = Noam | year = 1959 | title = On certain formal properties of grammars | journal = Information and Control | volume = 2 | issue = 2 | pages = 137–167 | doi = 10.1016/S0019-9958(59)90362-6 | refdoi-access = harv }}

* {{cite journal | first1=Michael J. | last1=Fischer | authorlink1=Michael J. Fischer | first2=Michael O. | last2=Rabin | authorlink2=Michael O. Rabin | date=1974 | title=Super-Exponential Complexity of Presburger Arithmetic | url=http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps | journal=Proceedings of the SIAM-AMS Symposium in Applied Mathematics | volume=7 | pages=27–41 | ref=harv }}

*{{cite journal | last1 = Oppen | first1 = Derek C. | year = 1978 | title = A 2^{2^{2^''pn''}} Upper Bound on the Complexity of Presburger Arithmetic | url = http://www.sciencedirect.com/science/article/pii/0022000078900211/pdf?md5=0415089a2d692fcece18b43b5f63c67d&pid=1-s2.0-0022000078900211-main.pdf | format = PDF | journal = J. Comput. Syst. Sci. | volume = 16 | issue = 3| pages = 323–332 | doi = 10.1016/0022-0000(78)90021-1 | doi-access = free }}

* {{Cite book |authorlast=Sipser | first = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | chapter = Decidability | pages = [https://archive.org/details/introductiontoth00sips/page/151 151–170] | isbn = 978-0-534-94728-X6 |ref author-link = harvMichael Sipser |postscript chapter-url-access = <!registration | chapter--None-->url = https://archive.org/details/introductiontoth00sips/page/151 }}

* {{Cite book | last=Sipser | first=Michael | year=2012 | title=Introduction to the Theory of Computation | publisher=Cengage Learning | chapter=The Church-Turing Thesis | pages=170 | isbn=978-1-133-18779-0 | author-link=Michael Sipser}}

{{Formal languages and grammars}}