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 nummererbart språk. Rekursive språk sies å være avgjørbare.

Alle rekursive språk er også rekursivt nummererbare. Alle regulære 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.$L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}$

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.

• Kleenestjerna av L
• Konkateneringa av L og P
• Bildet under en «e-free» homomorfisme
• Unionen av L og P
• Snittet av L og P
• Komplementet av L
• Mengdedifferansen 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

• 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.