Limbajul recursiv

În logica matematică și informatică , un limbaj recursiv este un tip de limbaj formal , numit și decidabil sau Turing decidabil . Clasa tuturor limbilor recursive este adesea notată cu R , deși aceeași denumire este folosită pentru clasa RP .

Acest tip de limbaj nu este definit în ierarhia Chomsky ( Chomsky 1959 ).

Definiții

Sunt folosite două definiții echivalente ale unui limbaj recursiv:

1. Un limbaj recursiv formal este un subset recursiv al setului tuturor cuvintelor posibile din alfabetul unui limbaj formal .
2. Un limbaj recursiv este un limbaj formal pentru care există o mașină Turing care se oprește la orice șir de intrare și o permite dacă și numai dacă aparține limbajului. Se spune că o astfel de mașină este un rezolvator și rezolvă limbajul recursiv dat.

Toate limbile recursive sunt, de asemenea, enumerabile recursiv . Toate limbile obișnuite , fără context și sensibile la context sunt recursive.

Proprietăți de închidere

Limbile recursive sunt închise în următoarele operațiuni. Astfel, dacă L și P sunt limbi recursive, atunci și următoarele limbi sunt recursive:

• Închidere Kleene ;
• imaginea lui , unde este un homomorfism astfel încât , unde este un șir gol;
• concatenare ;
• asociere ;
• intersecție ;
• adaos ;
• diferenta .

Referințe

• Michael Sipser Decidabilitatea // Introducere în teoria  calculului . - Editura PWS, 1997. - P.  151 -170. — ISBN 0-534-94728-X .
• Chomsky, Noam. Despre anumite proprietăți formale ale gramaticilor   // Informații și control : jurnal. - 1959. - Vol. 2 , nr. 2 . - P. 137-167 . - doi : 10.1016/S0019-9958(59)90362-6 .

Vezi și

• Limbaj enumerat recursiv