Megoldások a hatodik gyakorlathoz
1. (a) Egy nagy X, utána meg az input szó. (b) A palindrómákat, azaz az olyan szavakat, amik visszafele olvasva is ugyanazok. (c) Lesz két új állapot: q6 és q7. Amikor q5-be mennénk az eredeti géppel, akkor menjünk q6-ba és ebben az állpotban menjünk vissza a második szalag elejére, közben üresre írva, azaz törölve minden mezőt. Ha meglátjuk az X-et, akkor annak a helyére írjunk 1-et és menjünk q5-be. Ezzel elintéztük, hogy ha elfogadunk, akkor 1-et írunk az output szalagra (ami most a második). Kell még, hogy kiürítsük a második szalagot és írjunk 0-t, ha elutasítanánk. Ez az eredeti gépnél akkor van, ha q3-ban nem két egyformát olvasunk. Ezekre az esetekre az új gépnél menjünk q7-be, töröljük először végig jobbra a második szalagot, majd menjünk vissza az elejére és közben töröljünk, amíg X-et nem látunk, azt írjuk át 0-ra. Ezzel kész. 2. A jegyzetben le van írva. 3. A teljes feladatsorban szerepel a megoldás a Turing gépek 5. feladatnál. 4. A teljes feladatsorban szerepel a megoldás a Turing gépek 6. feladatnál. 5. Igen. A Turing gép, ami mindig megáll és épp ezeket a kódokat fogadja el a következő: először is leellenőrzi, hogy az adott szó ![]() 6. Megmutatjuk, hogy ha ez a nyelv rekurzív lenne, akkor rekurzív lenne a megállási nyelv is, azaz az azon ![]() Tegyük fel tehát, hogy van egy olyan M Turing gépünk, ami minden ![]() Az M Turing gép segítségével készítünk egy olyan M' Turing gépet, ami mindig megáll és akkor fogad el, ha az ![]() ![]() Tehát az M' TG elkészíti ezt az M'x gépet az ![]() A fentiek értelmében ez az M' gép mindig megáll és éppen a megállasi nyelvet fogadja el, ami nem lehetséges. 7. Adunk egy M' Turing gépet, ami elfogad egy x szót, ha van hozzá jó y, különben meg nem áll meg. Ez az M' gép arra az M gépre épül, ami az L nyelvet ismeri fel. Ez az M gép elfogadja az L szavait, a többi szóra meg vagy nem áll meg vagy elutasít. Lényegében végigpróbálgatjuk az összes y szót az x-hez és ha találunk jót, akkor elfogadjuk az x-et, ha nem akkor meg nem állunk meg. A jó y keresése a következő módon megy: felveszünk egy táblázatot, aminek a sorai a természetes számoknak felelnek meg, az oszlopai meg az ábécé feletti szavaknak (mondjuk lexikografikus sorrendben). Így a táblázat két irányban is végtelen. Ebben lépkedünk a jegyzetben is vázolt átlós eljárás szerint (először az(oka)t a ponto(ka)t látogatjuk végig, ahol a sor és oszlopindexek összege 1, aztán azokat ahol az összeg kettő, stb.) Ha az (i,j) mezőn vagyunk, akkor futtajuk az M gépet ![]() 8. A teljes feladatsorban szerepel a megoldás a Turing gépek 23. feladatnál. |