Ugrás a tartalomhoz

Formális nyelvek és automaták

Dömösi Pál, Falucskai János, Horváth Géza, Mecsei Zoltán, Nagy Benedek (2011)

Kempelen Farkas Hallgatói Információs Központ

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

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.

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 TM=(Q, T, V, q0, #, d, F) rendezett hetes, ahol Q a gép belső állapotainak (véges) halmaza, q0Q 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 → 2Q×V×{Bal, Jobb, Helyben} a gép mozgásfüggvénye, mint szokásos, 2Q×V×{Bal, Jobb, Helyben} jelöli a Q×V×{Bal, Jobb, Helyben} halmaz összes részhalmazainak halmazát.

Ha tehát a TM 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, av) 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=λ, uv=λ bármelyike előfordulhat.) Az (u, q, av) 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 uav, 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=q0 é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, av), 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, av), qQF pillanatnyi konfiguráció esetén {(q, a, Helyben)}=d(q, a), akkor azt mondjuk, hogy a TM Turing-gép a tekintett pillanatnyi konfigurációban egyszerű végtelen ciklusba esik.

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

φ(W)= ubqav, ha a, bV∖{#}
  ubq#, ha bV, a=#, v=λ
  #qav, ha ub=λ, aV∖{#}
  #q#, ha ub=v=λ, a=#.

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

(I) W2=(u, q ', ba 'v) és (q ', a ', Bal)∈d(q, a),

(II) W2=(uba ', q ', v) és (q ', a ', Jobb)∈d(q, a),

(III) W2=(ub, q ', a 'v) és (q ', a ', Helyben)∈d(q, a).

A W pillanatnyi konfigurációból a W ' pillanatnyi konfiguráció(a TM -ben) levezethető (jelekben WTM*W ', vagy röviden W*W ' ), ha van a pillanatnyikonfigurációknak olyan W0, …, Wn sorozata, hogy WiWi+1, i=0, …, n-1 mellett W0=W, Wn=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 TM Turing gép által elfogadottnyelven értjük az

L(TM)={wT*|(λ, q0, w)⇒*W, W végkonfiguráció }

nyelvet.

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

Tekintsünk egy TM=(Q, T, V, q0, #, d, F) és egy TM '=(Q ', T ', V ', q'0, #', d ', F ') Turing-gépet.Akkor mondjuk, hogy TM izomorf TM '- 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(q0)=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×{Bal, Jobb, Helyben} 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 {Bal, Jobb} 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:

TMk=(k, Q, T, V, q0, #, 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×VkQ×Vk×{Bal, Jobb, Helyben}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=({q0,q1,q2,q3,q4,q5,qa},{a,b},{a,b,#},q0,#,δ,{qa}), ahol δ a következő:
 
(q0,a,#,q1,J) Ha az első betű a, akkor q1 állapotba megy a gép                    
(q0,b,#,q2,J) Ha az első betű b, akkor q2 állapotba megy a gép
(q0,#,#,qa,J) Ha az első betű # (az üresszó van a szalagon), akkor qa állapotba megy a gép
 
(q1,a,a,q1,J)                    
(q1,b,b,q1,J)                    
(q1,#,#,q3,B) Végig megy a gép az input szón, majd annak utolsó betűjére áll q3 állapottal
 
(q2,a,a,q1,J)                    
(q2,b,b,q1,J)                    
(q2,#,#,q4,B) Végig megy a gép az INPUT szón, majd annak utolsó betűjére áll q4 állapottal
 
(q3,a,#,q5,B) Ha az utolsó betű a, akkor töröljük, és mehet a gép a szó elejére q5 állapottal
 
(q4,b,#,q5,B) Ha az utolsó betű b, akkor töröljük, és mehet a gép a szó elejére q5 állapottal
 
(q3,#,#,qa,B)                    
(q4,#,#,qa,B) Ha az input szó páratlan hosszú volt, akkor elfogadjuk
 
(q5,a,a,q5,B)                    
(q5,b,b,q5,B)               
(q5,#,#,q0,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={A2n | 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=({q0,q1,q2,q3,q4,qa},{A},{A,X,0,1,#},q0,#,δ,{qa}), ahol δ a következő:
 
(q0,A,X,q1,B) Az első A-t átírjuk X-re, majd eggyel balra lépünk
 
(q1,#,1,q2,J)
(q1,0,1,q2,J)
(q1,1,0,q1,B) A legbaloldalabbi X előtti bináris számot növeljük 1-gyel, majd q2 állapotba megyünk
 
(q2,1,1,q2,J)
(q2,0,0,q2,J)
(q2,X,X,q2,J)
(q2,A,A,q0,H) Megkeressük a legbaloldalabbi A-t, majd átmegyünk a kezdőállapotba
 
(q2,#,#,q3,B) Nincs több A, a fejtől balra csak X-ek és egy bináris számunk van. Átmegy a gép q3 állapotba. 
 
(q3,X,#,q3,B) Töröljük az X-eket
 
(q3,0,0,q3,B) A 0-kon átmegyünk q3 állapottal
 
(q3,1,1,q4,B) Ha egy 1-est találunk, átmegyünk q4-be
 
(q4,#,#,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={anbncnn ≥ 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 T3=({q0, q1, q2, q3, qa},{a,b,c}, {a,b,c,A,B,C,#},q0,#,δ,{qa}), ahol δ a következő:
 
(q0, #, #, qa, B) üresszón állunk q0-nál, akkor a beolvasott szót felismeri a gép
 
(q0, a, A, q1, J) a legbaloldalibb a-t átírjuk A-vá, és átmegyünk q1-be
 
(q0, B, B, q0, J)                    
(q0, C, C, q0, J) a B és C betűkön csak jobbra átmegyünk q0-lal
 
(q1, a, a, q1, J)                    
(q1, B, B, q1, J) az a-kon és a B-ken jobbra haladva átmegyünk az első b-ig
 
(q1, b, B, q2, J) a legbaloldalibb b-t átírjuk B-vé, és átmegyünk q2-be
 
(q2, b, b, q2, J)                    
(q2, C, C, q2, J) a b-ken és a C-ken jobbra haladva átmegyünk az első c-ig
 
(q2, c, C, q3, B) a legbaloldalibb c-t átírjuk C-vé, és átmegyünk q3-ba, majd balra lépünk egyet
 
(q3, a, a, q3, B)
(q3, b, b, q3, B)
(q3, c, c, q3, B)
(q3, B, B, q3, B)
(q3, C, C, q3, B) q3 állapottal elmegyünk a legbaloldalibb A-ig, majd jobbra lépünk 1-et
 
(q3, A, A, q0, J) az első A-t követő karakteren állunk kezdőállapotban.

Az L={anbncnn ≥ 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: