Rekursivt språk

Inom matematisk logik och datavetenskap är ett rekursivt språk en typ av formellt språk , även kallat avgörbart , eller Turing-avgörbart . Klassen för alla rekursiva språk betecknas ofta med R , även om samma beteckning används för klassen RP .

Denna typ av språk är inte definierad i Chomsky-hierarkin ( Chomsky 1959 ).

Definitioner

Två ekvivalenta definitioner av ett rekursivt språk används:

1. Ett formellt rekursivt språk är en rekursiv delmängd av mängden av alla möjliga ord i alfabetet för ett formellt språk .
2. Ett rekursivt språk är ett formellt språk för vilket det finns en Turing-maskin som stannar vid vilken inmatningssträng som helst och tillåter det om och bara om den tillhör språket. En sådan maskin sägs vara en lösare och löser det givna rekursiva språket.

Alla rekursiva språk är också rekursivt uppräknade . Alla vanliga , sammanhangsfria och sammanhangskänsliga språk är rekursiva.

Stängningsegenskaper

Rekursiva språk är stängda i följande operationer. Således, om L och P är rekursiva språk, är följande språk också rekursiva:

• Kleene stängning ;
• bilden av , där är en homomorfism sådan att , där är en tom sträng;
• sammanlänkning ;
• förening ;
• korsning ;
• tillägg ;
• skillnad .

Referenser

• Michael Sipser Beslutbarhet // Introduktion till teorin om  beräkning . - PWS Publishing, 1997. -  S. 151 -170. — ISBN 0-534-94728-X .
• Chomsky, Noam. Om vissa formella egenskaper hos grammatik   // Information och kontroll : journal. - 1959. - Vol. 2 , nr. 2 . - S. 137-167 . - doi : 10.1016/S0019-9958(59)90362-6 .

Se även

• Rekursivt uppräknat språk