Rekursive språk

I matematikk, informatikk og logikk er eit formelt språk eit rekursivt språk (òg kalla turingavgjerbart språk) om det eksisterer ei turingmaskin som vert sagt å avgjera språket. Med andre ord må det eksistera ei turingmaskin som for kvar og eitt input vil kunna stoppa. Om dette kravet ikkje er oppfylt, vert det i staden kalla for eit rekursivt nummererbart språk. Rekursive språk vert sagt å vera avgjerbare.

Alle rekursive språk er òg rekursivt nummererbare. Alle regulære språk, kontekstfrie språk og kontekstsensitive språk er òg rekursive språk.

Døme

Som skildra tidlegare, kvart og eitt kontekstsensitivt språk er eit rekursivt språk. Dermed vil det følgjande kontekstsensitive språket òg vera eit rekursivt språk.$L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}$

Eigenskapar

Rekursive språk er lukka under operasjonane lista nedanføre. Det vil altså seia at for to rekursive språk L og P, så vil resultatet av operasjonen framleis vera eit rekursivt språk.

• Kleenestjerna av L
• Konkateneringa av L og P
• Biletet under ein «e-free» homomorfisme
• Unionen av L og P
• Snittet av L og P
• Komplementet av L
• Mengddifferansen av L og P

Den siste eigenskapen følgjer av at snittet og komplementet er lukka operasjonar. Legg merke til at rekursive språk har monaleg fleire lukka operasjonar enn rekursivt nummererbare språk og andre språk lengre ned i Chomskyhierarkiet.

Litteratur

• Michael Sipser (1997). «Decidability». Introduction to the Theory of Computation. PWS Publishing. s. 151–170. ISBN 0-534-94728-X. 
• Chomsky, Noam (1959). «On certain formal properties of grammars». Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.