Content deleted Content added
→top: trying to make the sentence more readable: rephrase to singular; no need to emphasize alphabet here |
added examples |
||
Line 17:
By the second definition, any [[decision problem]] can be shown to be decidable by exhibiting 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, 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}}, 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.
== Closure properties ==
Line 38 ⟶ 46:
* {{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}}
* {{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<sup>2<sup>2<sup>''pn''</sup></sup></sup> 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 }}
{{Formal languages and grammars}}
| |||