Recursive language: Difference between revisions

Revision as of 05:50, 24 November 2015

Revision as of 16:50, 24 November 2015

Line 20:

== Examples ==

As noted above, every context-sensitive language is recursive. Thus, a simple example of a recursive language is the set {{math|1=''L''={{mset|''abc'', ''aabbcc'', ''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 {{math|''c'' > 0}} {{harv|Fischer|Rabin|1974}}. Here, {{mvar|''n}}'' denotes 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 {{mvar|''c}}'' {{citation needed|date=March 2015}}, 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 {{mvar|''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.

== Closure properties ==

Recursive languages are [[closure (mathematics)|closed]] under the following operations. That is, if {{mvar|''L}}'' and {{mvar|''P}}'' are two recursive languages, then the following languages are recursive as well:

* The [[Kleene star]] <math>L^*</math>

* The image {{math|φ(''L'')}} under an [[Homomorphism#Homomorphisms and e-free homomorphisms in formal language theory|e-free homomorphism]] {{mvar|φ}}

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

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

* The intersection <math>L \cap P</math>

* The complement of {{mvar|<math>L}} </math>

* The set difference <math>L - P</math>