Rekurzivni jezik

U matematici, logici i računarstvu, rekurzivni jezik je tip formalnog jezika koji se još zove i rekurzivan, odlučiv ili Turing-odlučiv. Klasa svih rekurzivnih jezika se često zove R, iako se to ime često upotrebljava i za klasu složenosti RP.

Ovaj tip jezika nije definiran u Chomskyjevoj hijerarhiji.

Definicije

U literaturi prevladavaju dvije istovjetne definicije koncepta rekurzivnog jezika:

1. Rekurzivni formalni jezik je rekurzivni podskup skupa svih mogući riječi nad abecedom jezika.
2. Rekurzivni jezik je formalni jezik za kojeg postoji Turingov stroj koji će, za svaki ulazni niz znakova (simbola) stati i prihvatiti niz ako je on element jezika, a inače ga neće prihvatiti. Turingov stroj uvijek staje - poznat i pod nazivom odlučitelj - i kažemo da odlučuje rekurzivni jezik.

Svi rekurzivni jezici su rekurzivno prebrojivi. Svi regularni, kontekstno neovisni i kontekstno ovisni jezici su rekurzivni.

Svojstva zatvorenosti

Rekurzivni su jezici zatvoreni nad sljedećim operacijama. To jest, ako su L i P dva rekurzivna jezika, tada su i sljedeći jezici također rekurzivni:

• Kleeneov operator Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L^*} jezika L
• neprebrisujući homeomorfizam φ(L) jezika L
• nadovezivanje (konkatenacija) Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L \circ P} jezika L i jezika P
• unija Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L \cup P}
• presjek Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L \cap P}
• komplement jezika L
• razlika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L - P}

Posljednje svojstvo slijedi iz činjenice da se razlika skupova može izraziti preko presjeka i komplementa.

Izvori

• Nepoznat parametar: chapter
• Nepoznat parametar: id
• Parametar pages nije dopušten u klasi book

• Nepoznat parametar: id

• Nepoznat parametar: id

• • Parametar type nije dopušten u klasi journal
  • Parametar first nije dopušten u klasi journal
  • Parametar last nije dopušten u klasi journal