Rekursiivisesti lueteltu kieli

Matematiikassa, logiikassa ja tietojenkäsittelytieteessä rekursiivisesti numeroitava kieli on eräänlainen muodollinen kieli, joka tunnetaan myös nimellä osittain ratkaistava tai Turingin tunnistettavissa oleva kieli . Chomsky - hierarkiassa se tunnetaan tyypin 0 kielenä. Kaikkien rekursiivisesti numeroitavien kielten luokkaa kutsutaan RE.

Määritelmät

Rekursiivisesti numeroituvan kielen käsitteelle on olemassa kolme pääasiallista vastaavaa määritelmää.

1. Rekursiivisesti numeroitava muodollinen kieli on rekursiivisesti numeroitava osajoukko kaikista mahdollisista kielen aakkosissa olevien sanojen joukosta .
2. Rekursiivisesti numeroitava kieli on muodollinen kieli, jolle on olemassa Turingin kone (tai muu laskettava funktio ), joka luettelee kaikki kielen kelvolliset merkkijonot. Huomaa, että jos kieli on ääretön, voidaan valita toistoa välttävä luettelointialgoritmi, koska n -numeroiselle merkkijonolle voidaan tarkistaa, onko se "jo" palautettu pienemmällä luvulla kuin n . Jos oli, käytä sen sijaan lähtönumeroa n+1 (rekursiivisesti) ja tarkista, onko se "uusi".
3. Rekursiivisesti numeroitava kieli on muodollinen kieli, jolle on olemassa Turingin kone (tai muu laskettava funktio ), joka pysähtyy ja hyväksyy minkä tahansa kielen syötemerkkijonon, mutta pysähtyy ja hylkää tai ei lopeta lainkaan syötemerkkijonoa, joka ei ole peräisin kielestä. . Rekursiiviset kielet edellyttävät Turingin koneen pysähtymistä joka tapauksessa.

Kaikki tavalliset, yhteydettömät, kontekstiherkät ja rekursiiviset kielet ovat rekursiivisesti luettavissa.

Postin lause osoittaa, että RE yhdessä ylimääräisen rinnakkaisRE:n kanssa vastaa aritmeettisen hierarkian ensimmäistä tasoa .

Sulkemisominaisuudet

Rekursiivisesti numeroitavat kielet suljetaan seuraavien toimintojen alla. Olkoon L ja P  kaksi rekursiivisesti numeroitavaa kieltä, niin myös seuraavat kielet ovat rekursiivisesti numeroituvia:

• Kleene - tähti L
• ketjutus L: stä ja P :stä
• yhdistys
• Risteys

Huomaa, että rekursiivisesti numeroitavia kieliä ei suljeta eron tai täydennyksen alle. Joukkoero L \ P voi olla rekursiivisesti numeroituva tai ei. Jos L on rekursiivisesti numeroituva, niin L :n komplementti on rekursiivisesti numeroituva jos ja vain jos L on myös rekursiivinen.

Kirjallisuus

Gladkiy A. V. Muodolliset kieliopit ja kielet. - M . : "Nauka", 1973. - 368 s.