Rekursiivinen kieli

Matemaattisessa logiikassa ja tietojenkäsittelytieteessä rekursiivinen kieli on eräänlainen muodollinen kieli , jota kutsutaan myös ratkaistavaksi tai Turingin pääteltäväksi . Kaikkien rekursiivisten kielten luokka on usein merkitty R :llä , vaikka samaa nimitystä käytetään luokassa RP .

Tämän tyyppistä kieltä ei ole määritelty Chomsky-hierarkiassa ( Chomsky 1959 ).

Määritelmät

Rekursiiviselle kielelle käytetään kahta vastaavaa määritelmää:

1. Formaali rekursiivinen kieli on rekursiivinen osajoukko kaikkien mahdollisten sanojen joukosta muodollisen kielen aakkosissa .
2. Rekursiivinen kieli on muodollinen kieli, jolle on olemassa Turingin kone , joka pysähtyy missä tahansa syötemerkkijonossa ja sallii sen jos ja vain jos se kuuluu kieleen. Sellaisen koneen sanotaan olevan ratkaisija ja se ratkaisee annetun rekursiivisen kielen.

Kaikki rekursiiviset kielet ovat myös rekursiivisesti numeroitavia . Kaikki tavalliset , yhteydettömät ja kontekstiherkät kielet ovat rekursiivisia.

Sulkemisominaisuudet

Rekursiiviset kielet suljetaan seuraavissa toiminnoissa. Siten, jos L ja P ovat rekursiivisia kieliä, myös seuraavat kielet ovat rekursiivisia:

• Kleene sulkeminen ;
• kuva , jossa on homomorfismi sellainen, että , jossa on tyhjä merkkijono;
• ketjutus ;
• yhdistys ;
• risteys ;
• lisäys ;
• ero .

Viitteet

• Michael Sipser Päättävyys // Johdatus  laskennan teoriaan . - PWS Publishing, 1997. - S.  151-170 . — ISBN 0-534-94728-X .
• Chomsky, Noam. Tietyistä kielioppien muodollisista ominaisuuksista   // Information and Control : päiväkirja. - 1959. - Voi. 2 , ei. 2 . - s. 137-167 . - doi : 10.1016/S0019-9958(59)90362-6 .

Katso myös

• Rekursiivisesti lueteltu kieli