Recursive language: Difference between revisions

Revision as of 23:28, 12 March 2015

Revision as of 05:49, 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 ==