Content deleted Content added
m Please do not add mvar to articles that don't have it already - it is not univerally desired nor recommended |
m →Examples: display math |
||
Line 20:
== Examples ==
As noted above, every context-sensitive language is recursive. Thus, a simple example of a recursive language is the set ''L={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 ''c''>0 {{harv|Fischer|Rabin|1974}}. Here, ''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 ''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 ''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.
| |||