Redigerer Rekursive språk

I [[matematikk]], [[informatikk]] og [[logikk]] er et [[formelt språk]] et '''rekursivt språk''' (også kalt '''turingavgjørbart språk''') hvis det eksisterer ei [[turingmaskin]] som sies å avgjøre språket. Med andre ord må det eksistere ei turingmaskin som for ethvert input vil kunne stoppe. Om dette kravet ikke er oppfylt, kalles det i stedet for et [[Rekursivt nummererbare språk|rekursivt nummererbart språk]]. Rekursive språk sies å være avgjørbare.

Alle rekursive språk er også rekursivt nummererbare. Alle [[Regulært språk|regulære språk]], [[Kontekstfritt språk|kontekstfrie språk]] og [[kontekstsensitive språk]] er også rekursive språk.

== Eksempel ==
Som beskrevet tidligere, ethvert kontekstsensitivt språk er et rekursivt språk. Dermed vil det følgende kontekstsensitive språket også være et rekursivt språk.<math>L=\{\,w \in \{a,b,c\}^* \mid w=a^nb^nc^n \mbox{ for some } n\ge 1 \,\}</math>

== Egenskaper ==
Rekursive språk er lukket under følgende operasjoner. Det vil altså si at for to rekursive språk L og P, så vil resultatet av operasjonen fortsatt være et rekursivt språk.
* [[Kleenestjerne|Kleenestjerna]] av L
* [[Konkatenering]]a av L og P
* Bildet under en «e-free» homomorfisme
* [[Union]]en av L og P
* [[Snitt (mengdelære)|Snittet]] av L og P
* [[Komplementet]] av L
* [[Mengdedifferanse]]n av L og P
Den siste egenskapen følger av at snittet og komplementet er lukkede operasjoner. Legg merke til at rekursive språk har betydelig flere lukkede operasjoner enn rekursivt nummererbare språk og andre språk lengre ned i [[Chomskyhierarkiet]].

== Litteratur ==
* {{Cite book|author=[[Michael Sipser]]|year=1997|title=Introduction to the Theory of Computation|url=https://archive.org/details/introductiontoth00sips_648|publisher=PWS Publishing|chapter=Decidability|pages=[https://archive.org/details/introductiontoth00sips_648/page/n164 151]–170|isbn=0-534-94728-X|ref=harv}}
* {{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}}

[[Kategori:Formelle språk]]
[[Kategori:Kompleksitetsteori]]