Rekursivt sprog

I matematisk logik og datalogi er et rekursivt sprog en form for formelt sprog , også kaldet decidable eller Turing decidable . Klassen for alle rekursive sprog betegnes ofte med R , selvom den samme betegnelse bruges til klassen RP .

Denne type sprog er ikke defineret i Chomsky-hierarkiet ( Chomsky 1959 ).

Definitioner

To ækvivalente definitioner af et rekursivt sprog bruges:

1. Et formelt rekursivt sprog er en rekursiv delmængde af mængden af ​​alle mulige ord i et formelt sprogs alfabet .
2. Et rekursivt sprog er et formelt sprog, for hvilket der er en Turing-maskine , der stopper ved enhver inputstreng og tillader det, hvis og kun hvis det hører til sproget. Sådan en maskine siges at være en løser og løser det givne rekursive sprog.

Alle rekursive sprog kan også tælles rekursivt . Alle almindelige , kontekstfrie og kontekstfølsomme sprog er rekursive.

Lukningsegenskaber

Rekursive sprog er lukket i følgende operationer. Således, hvis L og P er rekursive sprog, så er følgende sprog også rekursive:

• Kleene lukning ;
• billedet af , hvor er en homomorfi sådan at , hvor er en tom streng;
• sammenkædning ;
• forening ;
• kryds ;
• tilføjelse ;
• forskel .

Referencer

• Michael Sipser Afgørelighed // Introduktion til  beregningsteorien . - PWS Publishing, 1997. - S.  151 -170. — ISBN 0-534-94728-X .
• Chomsky, Noam. Om visse formelle egenskaber ved grammatikker   // Information og kontrol : journal. - 1959. - Bd. 2 , nr. 2 . - S. 137-167 . - doi : 10.1016/S0019-9958(59)90362-6 .

Se også

• Rekursivt opregnet sprog