9. fejezet - Rekurzívan felsorolható nyelvek és Turing-gépek

Ebben a fejezetben a mondatszerkezetű nyelvtanok által generált nyelvosztályt fogjuk megvizsgálni, vagyis azon nyelvek osztályát, amelyek generatív nyelvtannal generálhatóak.

A mondatszerkezetű nyelvtanok esetén a levezetéseket gráffal tudjuk szemléltetni hasonlóan a környezetfüggő, illetve a monoton esethez. Ezeket a továbbiakban nem részletezzük. Megjegyezzük viszont, hogy a gráf kinézete speciális lehet, ha különböző normálformát követelünk meg a nyelvtantól.

A fejezetben, ahogy a címben is szerepel, központi szerepet játszik a Turing-gép fogalma.

9.1. A Turing-gép

A Turing-gép (TM: Turing Machine) fogalmát Alan Turing (ejtsd: tyuring) vezette be bizonyos automatikusan végrehajtható számítások tanulmányozására 1936-ban, jóval az első programvezérlésű elektronikus számítógépek megjelenése előtt. Egyszerűsége ellenére a Turing-gép elég jó modellnek bizonyult bizonyos számítógépekkel kapcsolatos vizsgálatokban, így például a számítógépek számítási kapacitásának elvi korlátai kutatásában.

A Turing-gép egy potenciálisan végtelen szalagmemóriával és egy író-olvasó fejjel ellátott véges automata. A szalagmemória pozíciókra van osztva, s minden egyes pozíció mint memória-egység az úgynevezett szalagábécé pontosan egy betűjének tárolására képes. Kezdetben a Turing-gép egy specifikált kezdőállapotában van, s a szalagon egy véges hosszúságú input szó helyezkedik el. Az eddig tárgyalt automatákhoz hasonlóan ez a modell is szekvenciális működésű. Működésének kezdetekor a Turing-gép író-olvasó feje az input szó első betűjén áll. Az input szó előtti és utáni (végtelen sok) szalagpozíció egy speciális betűvel, a szóközzel (üres betűvel) van feltöltve, ami nem tévesztendő össze az üresszóval. Többek között azért is, hogy az input szó elkülöníthető lehessen a szalag többi részén tárolt mindkét irányban végtelen számú szóköztől, feltételezzük, hogy az input szó utolsó betűje nem lehet szóköz. Az input szó tehát az író-olvasó fej alatti betűtől (jobbra haladva) tart a szalag utolsó nem üres betűjéig. Speciálisan, üres input szó is elképzelhető. Ez esetben a szalag minden egyes pozíciója szóközzel van feltöltve, és az író-olvasó fej ezek egyikére mutat. (Utolsó szóköztől különböző betű pedig ekkor értelemszerűen nincs.) A Turing-gép diszkrét időskála mentén, elkülönített időpillanatokban hajt végre egy-egy elemi műveletet, mely az író-olvasó fej alatti betű olvasásából, ezen betű felülírásából, a belső állapot változtatásából, s az író-olvasó fej egy pozícióval való balra avagy jobbra mozgatásából, vagy éppen a fej helybenhagyásából áll. Amennyiben a Turing-gép eljut egy végállapotba, megáll.

Formálisan, a Turing-gép egy T M=(Q, T, V, q 0, #, d, F) rendezett hetes, ahol Q a gép belső állapotainak (véges) halmaza, q 0Q a kezdő állapot, V a szalagábécé, TV az inputábécé #∈(VT) a szóköz betű, FQ a végállapotok halmaza, d:Q×V → 2 Q×V×{B a l, J o b b, H e l y b e n} a gép mozgásfüggvénye, mint szokásos, 2 Q×V×{B a l, J o b b, H e l y b e n} jelöli a Q×V×{B a l, J o b b, H e l y b e n} halmaz összes részhalmazainak halmazát.

Ha tehát a T M Turing-gép egy qQ állapotában van és az író-olvasó fej alatt valamely aV jel áll, akkor- ha d(q, a) nem üres - a d(q, a)- beli hármasok egyikeszolgáltatja a gép operáció utáni új állapotát, a szalagjelet felülíró szimbólumot (mely nem feltétlen különböző a felülírt szimbólumtól), illetve az elmozdulás irányát. Ha d(q, a)=∅, azt úgy interpretáljuk, hogy ha a gép a q állapotban azíró-olvasó fej alatt az a betűt találja, további működésétfelfüggeszti (megáll).

Megjegyezzük, hogy bár a gép szalagját mindkét irányban végtelennek tekintjük, mindig csak véges sok #- tól különböző jel lehet rajta.

Vegyük észre, hogy a környezetfüggő nyelveknél definiált és tárgyalt lineárisan korlátozott automata (lásd LBA), tulajdonképpen a Turing-gép egy olyan változata, ahol a számításra fordítható szalagterület az input által lefoglalt területre korlátozódik. Ily módon a számítás bonyolultsága van korlátozva (lásd Bonyolultsági osztályok).

Az egyszerűbb írásmód kedvéért a továbbiakban fel fogjuk tételezni azt az egyébként megfelelő írásmóddal elérhető, ám jelentéktelen megszorítást, hogy QV=∅. Egy pillanatnyi konfiguráció (u, q, a v) alakú, ahol aV∪{λ}, u, vV *, qQ és uV + esetén u nem kezdődhet, vV + esetén pedig v nem végződhet szóközzel. (Természetesen u=λ, v=λ, u v=λ bármelyike előfordulhat.) Az (u, q, a v) konfiguráció azt jelenti, hogy a gép q belső állapotban van, miközben a feje éppen egy a jel felett áll, miközben a szalag "értelmes tartalma" éppen u a v, vagyis a szalagon u áll a fejtől balra és v jobbra (természetesen a bevezető, illetve folytató szóköz jeleket nem számítva).

Ha q=q 0 és u=λ akkor kezdőkonfigurációról, ha pedig qF, akkor végkonfigurációról beszélünk. (Sok esetben nem is szokták elkülöníteni a Turing-gép végállapotait a többi állapottól. Ilyenkor végkonfiguráció alatt azokat a (u, q, a v), konfigurációkat szokásérteni, ahol d(q, a)=∅. Ilyenkor a számítás "eredménye" a szalagról olvasható le a megálláskor.) Amennyiben valamely (u, q, a v), qQF pillanatnyi konfiguráció esetén {(q, a, H e l y b e n)}=d(q, a), akkor azt mondjuk, hogy a T M Turing-gép a tekintett pillanatnyi konfigurációban egyszerű végtelen ciklusba esik.

Minden egyes W=(u b, q, a v), qQ, u, vV *, aV, b∈(V∖{#})∪{λ} pillanatnyi konfigurációhoz (ahol ha u bλ, akkor u b nem kezdődhet, ha pedig vλ, akkor a v nem végződhet szóközzel) rendeljük hozzá a következőképp definiált φ(W) kifejezést.

φ(W)= u b q a v, ha a, bV∖{#}
  u b q#, ha bV, a=#, v=λ
  #q a v, ha u b=λ, aV∖{#}
  #q#, ha u b=v=λ, a=#.

Világos, hogy ez a hozzárendelés kölcsönösen egyértelmű. Mondjuk azt, hogy a W 1 pillanatnyi konfigurációból a W 2 pillanatnyikonfiguráció ( T M- ben) közvetlenül (vagy egy lépésben) levezethető(jelekben W 1 T M W 2, vagy ha egyértelmű mely TM gépről van szó, egyszerűbben W 1W 2 ),ha W 1=(u b, q, a v) eseténa következő feltételek valamelyike teljesül.

(I) W 2=(u, q ', b a 'v) és (q ', a ', B a l)∈d(q, a),

(II) W 2=(u b a ', q ', v) és (q ', a ', J o b b)∈d(q, a),

(III) W 2=(u b, q ', a 'v) és (q ', a ', H e l y b e n)∈d(q, a).

A W pillanatnyi konfigurációból a W ' pillanatnyi konfiguráció(a TM -ben) levezethető (jelekben W T M * W ', vagy röviden W* W ' ), ha van a pillanatnyikonfigurációknak olyan W 0, …, W n sorozata, hogy W i W i+1, i=0, …, n-1 mellett W 0=W, W n =W '. Speciálisan, minden W pillanatnyi konfigurációrafeltesszük W* W fennállását. Szokásosan, ha ki akarjuk hangsúlyozni,hogy W* W ' és WW ', használjuk a W+ W ' jelölést is. A T M Turing gép által elfogadottnyelven értjük az

L(T M)={wT *|(λ, q 0, w)⇒* W, W végkonfiguráció }

nyelvet.

11. Megjegyzés. Jelölje C T M a T M=(Q, T, V, q 0, #, d, F) Turing-gép összes pillanatnyi konfigurációinak halmazát. Vegyük észre, hogy a fentiekben tekintett T M Turing-gép által elfogadott nyelv egybeesik a következő G nyelvtan által elfogadott nyelvvel: G=(Q, T, q 0, H), ahol H=H 1H 2 és H 1={qλ|qF}, H 2={b q aφ(W)|qQ, b, a∈(V∖{#})∪{λ}, WC T M , (b, q, a)⊦W}.

Tekintsünk egy T M=(Q, T, V, q 0, #, d, F) és egy T M '=(Q ', T ', V ', q' 0, #', d ', F ') Turing-gépet.Akkor mondjuk, hogy T M izomorf T M '- vel, haaz állapotok és a szalagábécé betűinek alkalmas kölcsönösen egyértelmű átjelölésével a két gép meg fog egyezni. Formálisan, ha létezik olyan φ 1:QQ ' és φ 2:VV ' kölcsönösen egyértelmű leképezés-pár, hogy fennállnak a következők:

(i) φ 1(q 0)=q' 0, φ 2(#)=#';

(ii) minden qQ- ra qF akkor és csak akkor ha φ 1(q)∈F ';

(iii) valahányszor (p, b, Irány ) ∈d(q, a), mindannyiszor (φ 1(p), φ 2(b), Irány )∈d '(φ 1(q), φ 2(a)) és viszont.

Érvényes a következő tétel:

71. Tétel. A mondatszerkezetű nyelvek osztálya egybeesik a Turing gépek által elfogadott nyelvek osztályával.

Amennyiben a mozgásfüggvény képhalmaza a Q×V×{B a l, J o b b, H e l y b e n} halmaz (és nem annak részhalmazainak halmaza), akkor determinisztikus Turing gépről beszélünk, és érvényes a következő tétel.

72. Tétel. A determinisztikus Turing gépek által elfogadott nyelvek osztálya egybeesik a nemdeterminisztikus Turing gépek által elfogadott nyelvek osztályával.

A Turing-gépeknek több változata is ismert, most ezek közül mutatunk be néhányat.

Van olyan definíció, ahol a fej a {B a l, J o b b} irányokba léphet, és nem maradhat helyben. Belátható, hogy egy ilyen Turing-gép szimulálni tudja az eddigiekben ismertetett változatnak a fejet helyben hagyó lépéseit is: pl. egyet balra lép a fej, és egy olyan állapotba kerül az automata, amiben bármit is olvas a szalagon, azt nem változtatja meg, viszont jobbra visszalép és az eredeti automata állapotának megfelelelő állapotba kerül.

Ugyancsak szokásos a csak egyirányban végtelen szalagú Turing-gép használata, amelyik szintén képes az általános változat szimulációjára. Ekkor a szalag első karaktere egy speciális jel, amiből a gép rájön, hogy erre nem mehet tovább a fej. Ekkor egy olyan speciális állapotba kerül, aminek hatására jobbra lép, először leírja azt a jelet, ami eredetileg a speciális szimbólum helyére írt volna (ha a szalag mindkétirányban végtelen lenne), majd az itt olvasott karaktert eggyel jobbra, és így tovább, vagyis a szalag teljes (értelmes) tartalmát eggyel jobbra másolja, ezután (észlelve a felhasznált tárterület jobb szélét), a fej vissza mozog a baloldalra, aholis a gép folytatja az eredetileg tervezett számítását.

Sokszor az egyszerűbb leírás kedvéért többszalagos Turing-gépet használunk:

T M k =(k, Q, T, V, q 0, #, d, F) k- szalagos Turing-gép, ahol k∈ ℕ természetes szám, ennyi szalagja van aTuring-gépnek; és a d átmenetfüggvény alakja a következő: d:Q×V k Q×V k ×{B a l, J o b b, H e l y b e n} k .

Működését tekintve a többszalagos Turing-gép egy lépésben olvashat/írhat egyszerre több szalagra is. Kezdő konfigurációban az egyik szalagon (input-szalag) van a feldolgozandó adat, a többi szalag pedig üres. Többszalagos gépek esetén szokás egy szalagot az outputnak is fenntartani, ekkor a számítás végén azon a szalagon olvasható az eredmény, illetve sokszor az input szalag csak olvasható.

Minden többszalagos Turing-gép működése szimulálható egyszalagos Turing-géppel, vagyis egyszalagos Turing-gép is el tudja végezni azt a számítást amit egy többszalagos Turing-gép.

Megkülönböztethetünk kiszámító és eldöntő Turing-gépeket a következő definíció alapján.

Amennyiben a Turing-gép célja adott függvény kiszámítása a megadott bemenő értékekkel, akkor a gép a megállásakor az (output)szalagon a megfelelő eredményt hagyja. Ezzel szemben vannak olyan számítások, amikor a választ egy igen-nem kérdésre keressük, ezesetben eldöntő Turing-gépről beszélünk. Az eldöntő Turing-gépekkel lehet pl. egy L nyelvet elfogadtatni a következőképpen: bemenet egy wT * szó, a Turing-gép számításának eredménye pontosan akkor "igen" ha wL teljesül. (Ugyanez a hatás érhető el, ha csak akkor engedjük végállapotba jutni a gépet, ha elfogad.)

A következő ábrán egy kétszalagos Turing-gép vázlata látható.

A továbbiakban, ha mást nem mondunk, Turing-gép alatt determinisztikus Turing-gépet értünk. A példákban a fej mozgását jelentő szavakat azok kezdőbetűivel rövidítjük.

9.1. példa - Turing gépek 1.feladat


Adjunk meg olyan Turing-gépet, amely az {a,b} feletti tükörszavakat ismeri fel!
 


Megoldás:

Állapodjunk meg abban, hogy a kezdő konfigurációban az input szó első betűjén áll az író/olvasó fej,
és az input szó előtt és után "#" van.

Ha a Turing gép qi
               
 állapotban t-t olvas, v-t ír, átmegy qj
               
 állapotba és m irányba tovább lépteti a fejet, azaz
(qj,v,m)∈d(qi,t), akkor jelöljük ezt (qi,t,v,qj,m) ötössel! A fej mozgásának irányát pedig annak
kezdőbetűjével rövidítjük.
 
Legyen a T
               =({q
               0
               ,q
               1
               ,q
               2
               ,q
               3
               ,q
               4
               ,q
               5
               ,qa
               
},{a,b},{a,b,#},q
               0
               ,#,δ,{qa
               
}), ahol δ a következő:
 
(q
               0
               ,a,#,q
               1
               ,J) Ha az első betű a, akkor q
               1 állapotba megy a gép                    
(q
               0
               ,b,#,q
               2
               ,J) Ha az első betű b, akkor q
               2 állapotba megy a gép
(q
               0
               ,#,#,qa,J) Ha az első betű # (az üresszó van a szalagon), akkor qa
               
 állapotba megy a gép
 
(q
               1
               ,a,a,q
               1
               ,J)                    
(q
               1
               ,b,b,q
               1
               ,J)                    
(q
               1
               ,#,#,q
               3
               ,B) Végig megy a gép az input szón, majd annak utolsó betűjére áll q
               3 állapottal
 
(q
               2
               ,a,a,q
               1
               ,J)                    
(q
               2
               ,b,b,q
               1
               ,J)                    
(q
               2
               ,#,#,q
               4
               ,B) Végig megy a gép az INPUT szón, majd annak utolsó betűjére áll q
               4 állapottal
 
(q
               3
               ,a,#,q
               5
               ,B) Ha az utolsó betű a, akkor töröljük, és mehet a gép a szó elejére q
               5 állapottal
 
(q
               4
               ,b,#,q
               5
               ,B) Ha az utolsó betű b, akkor töröljük, és mehet a gép a szó elejére q
               5 állapottal
 
(q
               3
               ,#,#,qa,B)                    
(q
               4
               ,#,#,qa,B) Ha az input szó páratlan hosszú volt, akkor elfogadjuk
 
(q
               5
               ,a,a,q
               5
               ,B)                    
(q
               5
               ,b,b,q
               5
               ,B)               
(q
               5
               ,#,#,q
               0
               ,J) Újra a szó elejére és a kezdőállapotba megyünk!

A tükörszavakat felismerő Turing-gépet működés közben mutatja a következő ábra:

 


9.2. példa - Turing gépek 2.feladat


Adjunk meg olyan Turing-gépet, amely az L={A
               2
                     n
                  

               
 | n ≥ 0} nyelvet ismeri fel!
 


Megoldás:

Ezt a feladatot más oldalról közelítjük meg, mint elsőre az logikusnak tünne!
Első körben az A-k számát ábrázoljuk bináris formában, majd megnézzük,
hogy a kapott szám csak 1 darab 1-es számjegyet és utána esetleg 0-kat tartalmaz-e.
T
               =({q
               0
               ,q
               1
               ,q
               2
               ,q
               3
               ,q
               4
               ,qa
               
},{A},{A,X,0,1,#},q
               0
               ,#,δ,{qa
               
}), ahol δ a következő:
 
(q
               0
               ,A,X,q
               1
               ,B) Az első A-t átírjuk X-re, majd eggyel balra lépünk
 
(q
               1
               ,#,1,q
               2
               ,J)
(q
               1
               ,0,1,q
               2
               ,J)
(q
               1
               ,1,0,q
               1
               ,B) A legbaloldalabbi X előtti bináris számot növeljük 1-gyel, majd q
               2 állapotba megyünk
 
(q
               2
               ,1,1,q
               2
               ,J)
(q
               2
               ,0,0,q
               2
               ,J)
(q
               2
               ,X,X,q
               2
               ,J)
(q
               2
               ,A,A,q
               0
               ,H) Megkeressük a legbaloldalabbi A-t, majd átmegyünk a kezdőállapotba
 
(q
               2
               ,#,#,q
               3
               ,B) Nincs több A, a fejtől balra csak X-ek és egy bináris számunk van. Átmegy a gép q
               3 állapotba. 
 
(q
               3
               ,X,#,q
               3
               ,B) Töröljük az X-eket
 
(q
               3
               ,0,0,q
               3
               ,B) A 0-kon átmegyünk q
               3 állapottal
 
(q
               3
               ,1,1,q
               4
               ,B) Ha egy 1-est találunk, átmegyünk q
               4-be
 
(q
               4
               ,#,#,qa,H) Ha az 1-es előtt # van, akkor elfogadjuk a szót! ★
 


9.3. példa - Turing gépek 3.feladat


Adjunk meg olyan Turing-gépet, amely az L={anbncn
               
n ≥ 0} nyelvet ismeri fel!
 


Megoldás:
Az első a-t átírjuk A-vá, majd más állapotba megyünk, az első b-ig.
Az első b-t átírjuk B-vé, majd más állapotba megyünk, az első c-ig.
Az első c-t átírjuk C-vé, majd más állapotba megyünk visszafelé az első a-ig.
Az A,B,C betűkön csak tovább megyünk mindig.
Ha a végén csak # marad, akkor felismeri a gép a szót!
Legyen T
               3
               =({q
               0
               , q
               1
               , q
               2
               , q
               3
               , qa
               
},{a,b,c}, {a,b,c,A,B,C,#},q
               0
               ,#,δ,{qa
               
}), ahol δ a következő:
 
(q
               0
               , #, #, qa, B) üresszón állunk q
               0-nál, akkor a beolvasott szót felismeri a gép
 
(q
               0
               , a, A, q
               1
               , J) a legbaloldalibb a-t átírjuk A-vá, és átmegyünk q
               1-be
 
(q
               0
               , B, B, q
               0
               , J)                    
(q
               0
               , C, C, q
               0
               , J) a B és C betűkön csak jobbra átmegyünk q
               0-lal
 
(q
               1
               , a, a, q
               1
               , J)                    
(q
               1
               , B, B, q
               1
               , J) az a-kon és a B-ken jobbra haladva átmegyünk az első b-ig
 
(q
               1
               , b, B, q
               2
               , J) a legbaloldalibb b-t átírjuk B-vé, és átmegyünk q
               2-be
 
(q
               2
               , b, b, q
               2
               , J)                    
(q
               2
               , C, C, q
               2
               , J) a b-ken és a C-ken jobbra haladva átmegyünk az első c-ig
 
(q
               2
               , c, C, q
               3
               , B) a legbaloldalibb c-t átírjuk C-vé, és átmegyünk q
               3-ba, majd balra lépünk egyet
 
(q
               3
               , a, a, q
               3
               , B)
(q
               3
               , b, b, q
               3
               , B)
(q
               3
               , c, c, q
               3
               , B)
(q
               3
               , B, B, q
               3
               , B)
(q
               3
               , C, C, q
               3
               , B) q
               3 állapottal elmegyünk a legbaloldalibb A-ig, majd jobbra lépünk 1-et
 
(q
               3
               , A, A, q
               0
               , J) az első A-t követő karakteren állunk kezdőállapotban.

Az L={anbncn
               
n ≥ 0} nyelvet felismerő Turing-gép működés közben látható:


9.4. példa - Turing gépek 4. feladat

Készítsünk olyan Turing-gépet, amely egy bináris szám kettes komplemensét állítja elő.

Megoldás: