Limbaj recursiv

În matematică , logică și informatică teoretică , limbajele decisive sau recursive sunt o clasă de limbaje formale care corespunde clasei de probleme decisive . Există două definiții principale echivalente pentru această clasă:

1. Un limbaj recursiv este un limbaj pentru care există o mașină Turing care, având în vedere orice șir de intrare , se termină acceptând șirul dacă aparține limbii și se termină respingând șirul dacă nu.
2. Un limbaj recursiv este un subset recursiv al setului tuturor șirurilor posibile din alfabetul limbii .

Toate limbajele recursive sunt recursiv enumerabile . Toate limbile regulate , fără context și dependente de context sunt recursive. Este de remarcat faptul că această categorie nu are corespondent direct în clasificarea Chomsky .

Proprietăți de închidere

Setul de limbaje recursive este închis cu privire la următoarele operații:

1. Kleene stea
2. homomorfism (cu condiția ca șirul gol ε să nu fie utilizat)
3. concatenare
4. Uniune
5. intersecție
6. completa
7. (datorită 5 și 6) diferență

Elemente conexe

• Problemă decisivă
• Gramatică dependentă de context
• Limbaj recursiv enumerabil