Rekurzív nyelv

A matematikai logikában és a számítástechnikában a rekurzív nyelv a formális nyelv egy fajtája , amelyet eldönthetőnek vagy Turing-dönthetőnek is neveznek . Az összes rekurzív nyelv osztályát gyakran R -vel jelölik , bár ugyanazt a megnevezést használják az RP osztálynál is .

Ez a nyelvtípus nincs meghatározva a Chomsky-hierarchiában ( Chomsky 1959 ).

Definíciók

A rekurzív nyelv két egyenértékű definíciója használatos:

1. A formális rekurzív nyelv a formális nyelv ábécéjében található összes szó halmazának rekurzív részhalmaza .
2. A rekurzív nyelv olyan formális nyelv, amelyre létezik egy Turing-gép , amely bármely bemeneti karakterláncnál megáll, és akkor és csak akkor engedi meg, ha az a nyelvhez tartozik. Egy ilyen gépet megoldónak mondanak, és megoldja az adott rekurzív nyelvet.

Minden rekurzív nyelv is rekurzívan felsorolható . Minden szokásos , kontextus nélküli és környezetérzékeny nyelv rekurzív.

Bezárás tulajdonságai

A rekurzív nyelvek zárva vannak a következő műveletekben. Így, ha L és P rekurzív nyelvek, akkor a következő nyelvek is rekurzívak:

• Kleene zárás ;
• a , hol képe , ahol olyan homomorfizmus , hogy , hol üres karakterlánc;
• összefűzés ;
• egyesület ;
• kereszteződés ;
• kiegészítés ;
• különbség .

Hivatkozások

• Michael Sipser Dönthetőség // Bevezetés a  számításelméletbe . - PWS Kiadó, 1997. - P.  151 -170. — ISBN 0-534-94728-X .
• Chomsky, Noam. A nyelvtan bizonyos formális tulajdonságairól   // Információ és vezérlés : folyóirat. - 1959. - 1. évf. 2 , sz. 2 . - 137-167 . o . - doi : 10.1016/S0019-9958(59)90362-6 .

Lásd még

• Rekurzívan felsorolt ​​nyelv