9.5. Zártsági tulajdonságok

Ebben a fejezetben a rekurzívan felsorolható nyelvek zártsági tulajdonságait vizsgáljuk meg.

89. Tétel. A rekurzívan felsorolható nyelvek osztálya zárt a reguláris műveletekre nézve.

Bizonyítás. A bizonyítás során tételezzük fel, hogy L 1=L(G 1), L 2=L(G 2), ahol G 1=(N 1, T, S 1, H 1) és G 2=(N 2, T, S 2, H 2), N 1N 2=∅ ; valamint terminális csak A → a alakú szabályban fordul elő (AN 1N 2, aT). A bizonyítást az egyes műveletekre külön-külön végezzük el.

A fejezet hátralevő részében további halmazműveleteket vizsgálunk.

90. Tétel. A rekurzívan felsorolható nyelvek osztálya zárt a metszetképzésre.

Bizonyítás. Vegyük azokat a Turing-gépeket, amelyek elfogadják az L 1 és L 2 nyelveket olymódon, hogy a szalagnak csak az input által elfoglalt, illetve ettől jobbra eső részét használják. Készítsük most el azt a Turing gépet, amely először egy másolatot készít az inputról (vagyis a w inputból a w#w új inputot készíti el), majd a jobboldali másolaton végrehajtja (szimulálja) az L 1- et elfogadó gép számítását, elfogadás esetén letörli (vagyis szóközökkel felülírja) a szalagon hagyott részszámításokat csak a baloldali w- t meghagyva, amelyre az L 2- t elfogadó gép működését hajtja végre. Világos, hogy pont akkor fogja az így megkonstruált Turing-gép elfogadni az inputot, ha mindkét nyelvhez tartozó Turing-gép külön-külön is elfogadná. ∎

Hasonlóan, megfelelő Turing-gépek segítségével, bizonyíthatóak a rekurzív nyelvekre a zártsági tulajdonságok:

91. Tétel. A rekurzív nyelvek osztálya zárt a reguláris (unió, konkatenáció, Kleene-csillag) és a halmaz- (unió, metszet, komplementer) műveletekre.

Korábban már volt szó a rekurzív és a rekurzívan felsorolható osztályok különbözőségéről (lásd Szóprobléma - rekurzív és rekurzívan felsorolható nyelvek).

6. Következmény. A rekurzívan felsorolható nyelvek halmaza nem zárt a komplementerképzésre.