Rekurzívan felsorolt ​​nyelv

A matematikában, a logikában és az informatikában a rekurzívan felsorolható nyelv a formális nyelv egy fajtája, más néven részlegesen eldönthető vagy Turing-felismerhető . A Chomsky-hierarchiában 0-s típusú nyelvként ismert. Az összes rekurzívan felsorolható nyelv osztályát RE-nek nevezik.

Definíciók

A rekurzívan felsorolható nyelv fogalmának három fő ekvivalens definíciója létezik.

1. A rekurzívan felsorolható formális nyelv a nyelv ábécéjén keresztül lehetséges szavak halmazának rekurzívan felsorolható részhalmaza .
2. A rekurzívan felsorolható nyelv olyan formális nyelv, amelyhez létezik egy Turing-gép (vagy más kiszámítható függvény ), amely felsorolja a nyelv összes érvényes karakterláncát. Vegyük észre, hogy ha a nyelv végtelen, akkor választhatunk olyan felsorolási algoritmust, amely elkerüli az ismétlődéseket, mivel az n számozott karakterlánc esetén ellenőrizhető, hogy „már” n -nél kisebb számmal került-e vissza . Ha volt, akkor használja helyette az n+1 kimeneti számot (rekurzívan), ismét ellenőrizve, hogy "új"-e.
3. A rekurzívan felsorolható nyelv olyan formális nyelv, amelyhez létezik egy Turing-gép (vagy más kiszámítható függvény ), amely megáll, és elfogad bármilyen bemeneti karakterláncot a nyelvből, de megáll és elutasít, vagy egyáltalán nem áll meg minden olyan bemeneti karakterlánc esetében, amely nem a nyelvből származik. . A rekurzív nyelvek megkövetelik, hogy a Turing-gép mindenképpen leálljon.

Minden reguláris, kontextusmentes, környezetérzékeny és rekurzív nyelv rekurzívan felsorolható.

Post tétele azt mutatja, hogy az RE a további társ-RE-vel együtt az aritmetikai hierarchia első szintjének felel meg .

Bezárás tulajdonságai

A rekurzívan felsorolható nyelvek a következő műveletek alatt záródnak. Legyen L és P  két rekurzívan megszámlálható nyelv, akkor a következő nyelvek is rekurzívan felsorolhatók:

• Kleene sztárja L
• összefűzés L - ből és P -ből
• egy egyesület
• útkereszteződés

Vegye figyelembe, hogy a rekurzívan felsorolható nyelvek nincsenek zárva a különbség vagy kiegészítés alatt. Az L \ P halmazkülönbség lehet rekurzívan megszámlálható, de lehet, hogy nem. Ha L rekurzívan megszámlálható, akkor L komplementere akkor és csak akkor rekurzívan megszámlálható, ha L is rekurzív.

Irodalom

Gladkiy A. V. Formális nyelvtanok és nyelvek. - M . : "Nauka", 1973. - 368 p.