7.5. Veremautomaták

Ha a véges automata definíciójában az állapothalmaz végességére vonatkozó követelményt elhagyjuk, akkor (a véges ábécéjű) végtelen automata fogalmához jutunk. Ez a fogalom e formájában túl általánosnak bizonyult, ezért bevezették a végtelen automaták speciális fajtáit.

7.19. példa - Verem működése

Az egyetemi menzán az ételeket tálcán szokás a kiszolgáló pultoktól az asztalokhoz vinni. A tálcák a kiszolgáló pultoknál egymás tetején vannak elhelyezve, s mindig csak a legfelső tálcát lehet elvenni. Ha a legfelső tálca valamiért nem szimpatikus (színe vagy más miatt), ahhoz hogy az alatta levő valamelyik tálcához hozzáférjünk, le kell venni a legfelsőt, s félretenni. Ezt a mozdulatot mindaddig folytatnunk kell, míg a kívánt (valamiért szimpatikus) tálcához nem jutunk. Ezután (ha rendeseknek akarunk látszani) akkor a félretett tálcákat visszapakoljuk (többnyire fordított sorrendben mint ahogy elvettük) úgy, hogy minden visszapakolt tálca fölé helyezzük a következő visszapakolandót. ★


A veremautomatát eredetileg aritmetikai kifejezések számítógéppel történő kiértékelésére vezették be, s történeti érdekessége, hogy egy veremautomatát realizáló szoftver volt az első olyan számítógépes szoftver termék, mely szabadalmi oltalmat kapott az USA-ban. Egyben ez volt a világon az első szoftver szabadalom. (A szabadalmaztatás a hatvanas években történt.)

A verem olyan alapvető adatszerkezet, amely fontos szerepet játszik a programozás során is. A számítógép, anélkül, hogy erre konkrét veremkezelő utasításokat használnánk alkalmazza a verem adatszerkezetet a rekurzív programozási módszerek esetén. Tekintsük a következő C-szerű pszeudo-kódot, amely a jól ismert Hanoi-tornyai probléma megoldására írodott.

7.20. példa - Verem, mint rekurziós eszköz

Adott n páronként különböző méretű korong és három rúd. Kezdetben mind az n korong az első (source) rúdon van. Bármelyik rúdon bármelyik pillanatban a korongok csak méretüknek megfelelő sorrendben lehetnek: adott korong alatt nála kisebb sohasem lehet. A cél hogy az összes n korongot átrakjuk az első rúdról a második (target) rúdra a harmadik (help) rúd alkalmas segítségével, oly módon, hogy minden lépésben egy korongot (a legfelsőt) tudjuk áthelyezni egy rúdról egy másik tetejére az előbb ismertetett feltételt betartva. A megoldás során egyes rudakhoz, mint verem adatszerkezethez tudunk hozzáférni.




               
function Hanoi (n,s,t,h){
 if (n>0){
 Hanoi (n-1,s,h,t);
 movedisk (s,t);
 Hanoi (n-1,h,t,s);}
}


Magyarázat: a Hanoi(n,s,t,h) hívásával n korongot helyezünk át az s rúdról a t rúdra úgy,
hogy közben a h rudat segédrúdként használhatjuk.

Másrészt a megoldás során a rekurzív hívások ugynacsak egy verem segítségével hajtódnak végre, mindig a megfelelő helyre visszadva a vezérlést. Ahogy az előző kód kompaktságán is látszik a rekurzió segítségével nagyon tömör forráskóddal tudunk feladatokat megoldani. ★

A veremautomata esetén egy potenciálisan végtelen befogadóképességű veremmemória összes lehetséges tartalma eredményez végtelen sok állapotot. A veremmemóriát úgy képzelhetjük el, mint egy pozíciókra felosztott, egyirányban végtelen szalagot.

Minden pozícióba egy-egy jel írható. A jelek kiolvasása, illetve törlése a bevitelhez képest fordított sorrendben történik (LIFO: Last In First Out adatszerkezet). Más szóval, a verem belsejének tartalmához közvetlenül nem férünk hozzá, hanem mindig csak a verem tetején lévő jelet tudjuk kiolvasni, illetve módosítani (felülírni, vagy törölni) és csak a verem tetejére (a benn lévők fölé) helyezhetünk el újabb jelet.

A verem alján kezdetben csak egy speciális szimbólum van, a kezdő veremszimbólum.

Általában az input szalaggal ellentétben, amit vízszintesen elhelyezkedőnek gondolunk, a vermet legtöbbször függőleges elrendezésűnek képzeljük/rajzoljuk. A formális leírásunkban a hellyel való takarékosság miatt, vízszintesen úgy fogjuk elképzelni, hogy a legelső betű a legfelső; vagyis mintha ez a szalag balra volna végtelen.

A veremautomata a véges bemenő szót egy input szalagon kapja meg, melyről egy olvasófejjel, balról jobbra haladva betűnként tudja leolvasni a bemenő szót. Az is megengedett, hogy az input szalag üres legyen, azaz az üresszót tartalmazza.

A veremautomatához a potenciálisan végtelen veremmemórián és az input szalagon kívül tartozik még egy véges iniciális nemdeterminisztikus kimenő jel nélküli automata, mely az input szalagról beolvasott betű, a verem tetején levő betű, valamint a belső állapota alapján fogja a verem tetejét és belső állapotát megváltoztatni. Az is megengedett, hogy egy-egy ilyen elemi lépés során az input szalagon a soron következő betűt ne vegye figyelembe, és/vagy az átmenet lényegében ne függjön a verem tetején lévő betűtől. Azt az elemi lépést, mikor a veremautomata az input szalagon soron következő betűt nem olvassa be (az olvasó fej helyben marad), λ- lépésnek is szokás hívni. Ezt a véges iniciális nemdeterminisztikus kimenő jel nélküli automatát a fejezet további részében a rövidség kedvéért a vereamutomata véges automatájának (vagy véges vezérlőjének) hívjuk.

A veremautomata működésének kezdetekor a verem szinte üres (csak a kezdő veremszimbólum van a verem alján), az input szalag olvasófeje a szalag első betűjére mutat (vagy ha az input szalag tartalma az üresszó, ezt érzékeli), s a veremautomatához tartozó véges automata pedig a kezdő állapotában van.

A működés veremautomata esetén is diszkrét időskála mentén haladva történik. Ha a veremautomatához tartozó véges automata a működés során a teljes input elolvasásával eljut egy végállapotba, akkor veremautomata megáll. A veremautomata megáll akkor is, ha a hozzá tartozó véges automata egy olyan állapotban van, melyhez nem tartozik egyetlen alkalmas átmenet sem. Az alkalmas átmenet létezése azt jelenti, hogy a verem tetején lévő jel figyelembe vételével vagy anélkül és az input szalagon lévő következő betű (ha van olyan) figyelembe vételével vagy anélkül az adott állapotból van lehetséges átmenet egy másik állapotba a veremautomata véges automatájában. A veremautomatához tartozó véges automata belső állapotát a továbbiakban röviden a veremautomata belső állapotának, vagy a veremautomata állapotának mondjuk. (Szigorúan véve a veremautomata belső állapotát egy pár határozza meg, melynek első eleme a verem tartalma, a második pedig a veremautomatához tartozó véges automata belső állapota, s így tekintve a veremautomata végtelen.)

Ha az input szalagon egy nem üresszó van, s a veremautomata úgy áll meg végállapotban, hogy előzőleg az input szalag utolsó betűjét is beolvasta, akkor azt mondjuk, hogy a veremautomata az input szalagon levő szót elfogadta. Ha a veremautomata úgy áll meg végállapotban, hogy az input szalag tartalma az üresszó, akkor azt mondjuk, hogy a veremautomata az üresszót elfogadta. Akkor mondjuk, hogy a (nemdeterminisztikus működésű) veremautomata egy bemenő szót elfogad, ha van olyan futása (működésmódja), hogy a bemenő szót elfogadja. A veremautomata által elfogadott bemenő szavak összeségét a veremautomata által elfogadott nyelvnek hívjuk. A veremautomatáknak többféle definíciója is ismert, a következőkben többféle (általánosabb és egyszerűbb modellt is megvizsgálunk). Látni fogjuk, hogy a veremautomaták által elfogadott nyelvek osztálya épp a környezetfüggetlen nyelvek osztálya.

Formálisan, egy veremautomata (PushDown Automaton) a következő hetes: P D A=(Q, T, Z, q 0, Z 0, d, F) ahol

Q a belső állapotok nem üres és véges halmaza, vagy más néven állapot ábécé,

T az inputábécé, vagy szalagábécé,

Z a veremábécé,

q 0Q a veremautomata kezdő állapota,

Z 0Z a verem kezdőjele ("alja"),

d leképezés a Q×(T∪{λ})×Z- ból a Q×Z * véges részhalmazaiba a (nemdeterminisztikus) átmeneti függvény,

FQ a veremautomata végállapotainak halmaza.

Egy veremautomata pillanatnyi konfigurációján értjük azt a (u, q, z) hármast, ahol uT * az input még fel nem dolgozott része, zZ * a veremmemória pillanatnyi tartalma ( z első betűje a verem tetején lévő betű), qQ pedig a veremautomata pillanatnyi belső állapota. Egy veremautomata minden lépésben a pillanatnyi konfigurációból a d átmeneti függvény definíciója értelmében egy vagy több pillanatnyi konfigurációba mehet át (vagy épp nem mehet át egybe sem). Mint már említettük, az átmenet történhet oly módon, hogy közben a veremautomata nem kéri a bemenő jelsorozat következő jelét ( λ- lépés).

A P D A veremautomata egy (a u, q, X z)∈(T *×Q×Z +) konfigurációt egy lépésben átalakít a (u, p, t z)∈(T *×Q×Z *) konfigurációba, ahol a∈(T∪{λ}), XZ pedig a verem tetején levő szimbólum, (jelekben: (a u, q, X z)⊦ P D A (u, p, t z), vagy csak egyszerűen: (a u, q, X z)⊦(u, p, t z)), ha van olyan aT∪{λ}, p, qQ, valamint tZ *, hogy a következő összefüggés fennáll: (p, t)∈d(q, a, X).

Egy veremautomata a (u, q, z)∈(T *×Q×Z +) konfigurációt (véges lépésben) átalakít (átalakíthat) a (v, p, t) konfigurációba - jelekben: (u, q, z)⊦*(v, p, t) - ha van olyan véges konfigurációsorozat P 0, P 1, …, P n , melyenk első tagja P 0=(u, q, z), utolsó tagja P n =(v, p, t), és bármely két egymást követő tagjára P i P D A P i+1 (i=0,…,n-1) fennáll.

A veremautomata által (végállapottal) elfogadott nyelv:

L(P D A f )={wT *|(w, q 0, Z 0)⊦*(λ, p, z) valamely zZ * és pF esetén }.

Látható, hogy a veremautomata egy lépésben egy jelpáron tud operációt végrehajtani, aholis a jelpár egyik tagja a veremábécé egy jele, a második tagja pedig az input ábécé egy betűje, vagy az üresszó.

Az eddigiek során a veremautomata végállapottal fogadta el a nyelvet, a szakirodalomban ugyanilyen jól ismert az üres veremmel elfogadó automata. Sok esetben, mint pl. a rekurzív programok esetén is, akkor tekintjük a rendszer működését helyesen befejezettnek, ha végül kiürül a verem.

Egy P D A=(Q, T, Z, q 0, Z 0, d, F) veremautomata üres veremmel fogadja el az

L(P D A e )={wT *|(w, q 0, Z 0)⊦*(λ, p, λ) valamely pQ esetén } nyelvet.

Egy üres veremmel elfogadó veremautomata esetén (vagyis ha az L(P D A e ) nyelvre vagyunk kíváncsiak), tulajdonképpen az F végállapotok halmazára nincs is szükség.

A veremautomatákat is megadhatjuk grafikusan a véges automatákhoz hasonló módon: körökkel jelöljük az állapotokat, külön (egy bemenő nyíllal) megjelölve a kezdőállapotot. Végállapottal elfogadó automata esetén duplakarikákkal jelöljük a végállapotokat, üres veremmel elfogadó automata esetén pedig nincs végállapot (vagyis a végállapotok hiányával jelezzük, hogy üresveremmel elfogadásról van szó). A d átmenetfüggvény alapján, ha (p, t)∈d(q, a, X), akkor egy irányított él vezet a q állapotból a p állapotba és az élen az (a, X/t) címke ( aT∪{λ}, XZ, tZ * ) mutatja, hogy az átmenet akkor lehetséges ha a- t olvasunk az input szalagról miközben X van a verem tetején, amit az átmenet során a t- vel helyettesítünk.

Egy tetszőleges veremautomata esetén a végállapottal, illetve az üres veremmel elfogadott nyelvek nagyon különbözhetnek egymástól. Ezért nagyon fontos, hogy, ha adva van egy veremautomata, akkor legyen adott az is, hogy mely módon akarjuk azt nyelv elfogadásra használni.

7.21. példa - Végállapottal elfogadó veremautomata működése

Olyan veremautomata működés közben, mely az a n b n alakú szavakat fogadja el:


7.22. példa - Az azonos számú a és b betűből álló szavakat végállapottal elfogadó veremautomata

A következő veremautomata olyan szavakat fogad el, melyekben az a- k és b- k száma megegyezik.


7.23. példa - A Dyck nyelvet végállapottal elfogadó automata

Az alábbi veremautomata a helyes zárójelek nyelvét (Dyck nyelvet) fogadja el.


A következőkben megmutatjuk, hogy a veremautomákkal végállapottal elfogadott nyelvek osztálya megegyezik a veremautomákkal üres veremmel elfogadott nyelvek osztályával. Az állítást két részben, konstruktívan bizonyítjuk.

49. Tétel. Legyen L nyelv olyan amit a P D A f veremautomata végállapottal elfogad. Ekkor van olyan P D A e veremautomata amely ugyanezt a nyelvet üres veremmel fogadja el.

Bizonyítás. Legyen P D A f =(Q, T, Z, q 0, Z 0, d, F). Ekkor megkonstruálunk egy P D A e =(Q ', T, Z ', q' 0, Z' 0, d ', ∅) automatát a következőképpen:

Q '=Q∪{q' 0, q f }, ahol q' 0, q f Q ;

Z '=Z∪{Z' 0}, ahol Z' 0Z;

d '- t pedig a következőképpen származtatjuk d- ből.

Legyen d '(q' 0, Z' 0)={(q 0, Z 0 Z' 0)}. Továbbá, minden p, qQ, aT∪{λ}, XZ, tZ * esetén, legyen (p, t)∈d '(q, a, X) pontosan akkor, ha (p, t)∈d(q, a, X); valamint legyen (q f , λ)∈d '(q, λ, X) minden q∈(F∪{q f }) és XZ ' esetén.

Az így konstruált P D A e automata első lépése csak az lehet, hogy átmegy a szimulálandó P D A f kezdőállapotának megfelelő állapotba, miközben a verembe a P D A f kezdő veremszimbóluma bekerül a P D A e kezdő veremszimbóluma fölé.

Ezután az automata a P D A f automata egy futását szimulálja, amíg az egy végállapotba nem jut vagy el nem akad.

Ha a P D A f egy végállapotba jutna, akkor, és csak ekkor, a P D A e automata átmehet a q f állapotba input olvasása nélkül, és kiürítheti a verem tartalmát.

P D A e pontosan akkor fogad el egy szót, ha a szimulálandó P D A f végigolvasta a szót és ekkor végállapotba került, vagyis pontosan a kívánt nyelvet fogadja el. ∎

50. Tétel. Legyen L nyelv olyan amit a P D A e veremautomata üres veremmel elfogad. Ekkor van olyan P D A f veremautomata amely ugyanezt a nyelvet végállapottal fogadja el.

Bizonyítás. Legyen P D A e =(Q, T, Z, q 0, Z 0, d, F). Ekkor megkonstruálunk egy P D A f =(Q ', T, Z ', q' 0, Z' 0, d ', {q f }) automatát a következőképpen:

Q '=Q∪{q' 0, q f }, ahol q' 0, q f Q ;

Z '=ZZ' 0, ahol Z' 0Z;

d '- t pedig a következőképpen származtatjuk d- ből.

Legyen d '(q' 0, Z' 0)={(q 0, Z 0 Z' 0)}. Továbbá, minden p, qQ, aT∪{λ}, XZ, tZ * esetén, legyen (p, t)∈d '(q, a, X) pontosan akkor ha (p, t)∈d(q, a, X). Ezen kívül legyen (q f , λ)∈d '(q, λ, Z' 0) minden qQ esetén.

Az így konstruált P D A f automata első lépése csak az lehet, hogy átmegy a szimulálandó P D A e kezdőállapotának megfelelő állapotba, miközben a verembe a P D A e kezdő veremszimbóluma bekerül a P D A f kezdő veremszimbóluma fölé.

Ezután az automata a P D A e automata egy futását szimulálja, amíg annak verme ki nem ürül (ekkor most Z' 0 a veremtartalom) vagy el nem akad.

Ha a szimulálandó verem kiürült, és csak ekkor, a P D A f átmehet végállapotba.

P D A f pontosan akkor fogad el egy szót, ha a szimulálandó P D A e végigolvasta a szót és ekkor kiürült a verme, vagyis pontosan a kívánt nyelvet fogadja el. ∎

Az előző konstrukcióval kicsit többet is beláttunk a tervezettnél: minden a veremautomaták által elfogadodtt L nyelvhez van olyan PDA veremautomata, amely L-et fogadja el végállapottal és üres veremmel is, ráadásul egyszerre végállapottal és üresveremmel fogadja el L minden szavát (és csak ezeket).

3. Következmény. A veremautomatákkal végállapottal elfogadott nyelvek osztálya megegyezik a veremautomákkal üres veremmel elfogadott nyelvek osztályával.

A következőkben a veremautomaták és a környezetfüggetlen nyelvosztály kapcsolatára derítünk fényt.

51. Tétel. Minden környezetfüggetlen L nyelvhez megadható egy PDA veremautomata, amely L-et fogadja el üres veremmel.

Bizonyítás. Legyen adott G=(N, T, S, H) környezetfüggetlen nyelvtan, amely L-et generálja. Ekkor definiáljuk P D A=(Q, T, Z, q, Z 0, d, ∅)- t a követekezőképpen:

legyen Q={q};

T ábécé megegyezik a G nyelvtannál megadott terminális ábécével, hiszen ugyanazt az L nyelvet szeretnénk elfogadtatni, amit G generál;

Z=NT; Z 0=S ; d-t pedig a H alapján a következőképpen definiáljuk:

legyen (q, t)∈d(q, λ, a) pontosan akkor, ha A → tH ezen kívül legyen (q, λ)∈d(q, a, a) minden aT- re.

Könnyen belátható, hogy az automata a w szó elfogadása során annak egy legbalodali levezetését szimulálja. ∎

Az előző konstrukcióban egy állapottal dolgoztunk, tulajdonképpen állapotra így nincs is szükség. Állapotnélküli veremautomatáról beszélünk, ha az eredeti definíciónknak megfelelő automatának csak egy állapota van. Világos hogy ilyen automaták esetén az elfogadás üres veremmel történik. Bevezethetjük a következő rövidítést: P D A n =(T, Z, Z 0, d)- vel jelöljük az üres veremmel elfogadó állapotnélküli veremautomatát (egyszerűen elhagyva a hetesből, illetve a d leképezésből az állapotokat). Az előző tétel bizonyításával, a tételnél erősebb állítást bizonyítottunk be: minden környezetfüggetlen nyelv üres veremmel elfogadtatható állapotnélküli veremautomatával.

Ha az előbbi konstrukciót speciális, pl. Chomsky vagy Greibach normálalakú nyelvtanra végezzük el, akkor megspórolhatóak azok a lépések, amelyek a terminálisokat a verembe helyezik (ha a verem tetején terminális van, akkor csak olyan lépés következhet, ami ezt kiveszi onnan, miközben a szalagról olvasunk).

Chomsky-féle normálalakú G=(N, T, S, H) nyelvtan esetén a P D A n =(T, N, S, d) fogadja el a nyelvet ahol λd(a, A) pontosan akkor, ha A → aH és B Cd(λ, A) pontosan akkor, ha AB CH.

Greibach normálforma használata esetén td(a, A) pontosan akkor, ha Aa tH valamely AN, aT, tN * esetén.

Ezek alapján gondolhatnánk azt, hogy ha állapotokat is megengedünk, akkor a veremautomaták a környezetfüggetlen nyelveknél bővebb nyelvosztály elfogadására képesek. Ezzel ellentétben belátható, hogy az állapotok szimulálhatóak állapotnélküli automatával is (a veremábécé megfelelő kitejesztésével). Nem az állapotnélküli és állapotokkal rendelkező automaták ekvivalenciáját fogjuk közvetlenül bizonyítani, hanem tetszőleges PDA veremautomatához megkonstruáljuk azt a környezetfüggetlen nyelvtant, amit PDA elfogad üres veremmel.

52. Tétel. Minden PDA veremautomatához létezik olyan G környezetfüggetlen nyelvtan, hogy L(P D A e )=L(G).

Bizonyítás. Legyen tehát P D A=(Q, T, Z, q 0, Z 0, d, F) adott. Készítsük el a G=(N, T, S, H) nyelvtant a következő módon. Legyen N={[p, X, q] | p, qQ, XZ}∪{S}. A szabályok pedig legyenek:

- S → [q 0, Z 0, q] minden qQ- ra.

- [p, X, q] → a[q 1, Y 1, q 2][q 2, Y 2, q 3]…[q n , Y n , q] minden lehetséges q 1, q 2, …, q n - re ( n ≥ 1 ), ha (q 1, Y 1Y n )∈d(p, a, X)

- [p, X, q] → a pontosan akkor, ha (q, λ)∈d(p, a, X).

Az első lépésben nemdeterminisztikusan megtippeljük az utolsó állapotot az elfogadáskor. A második lépésbeli szabályokkal nemdeterminisztikusan tippelünk a közbülső q 2, …, q n állapotokra. Ekkor indukcióval megmutatható, hogy pontosan akkor lesz termináló levezetés G-ben egy w szóra, ha azt a PDA automata elfogadja. ∎

4. Következmény. A környezetfüggetlen nyelvek osztálya egybeesik a veremautomaták által (akár végállapottal, akár üres veremmel, akár egyszerre mindkettővel) elfogadott nyelvek osztályával.

7.24. példa - Állapotnélküli, üres veremmel elfogadó automata működése és a legbaloldalibb levezetés kapcsolata

Legyen G=({S},{1,+},S,{S  → S+S, S  → 1}). A következő ábrákon egy, a G-vel ekvivalens veremautomata működése, mellette pedig egy G-beli legbaloldalibb levezetési fa felépülése látható.


A veremautomata üres veremmel elfogadta az 1+1+1+1 szót:

A továbbiakban a veremautomaták néhány speciális változatát vizsgáljuk meg.

Ha a P D A=(Q, T, Z, q 0, Z 0, d, F) olyan, hogy

- minden pQ, aT és XZ esetén fennáll, hogy |d(p, λ, X)|+|d(p, a, X)| ≥ 1 (vagyis nem lehet üresszavas átmenet értelmezve olyan állapot és veremszimbólum párra, amire van értelmezve nem üresszavas átmenet is), valamint

- minden pQ, aT∪{λ} és XZ esetén |d(p, a, X)| ≥ 1 (vagyis maximum egyféle átmenet van értelmezve),

akkor determinisztikus veremautomatáról beszélünk. Érvényes a következő tétel.

53. Tétel. A determinisztikus veremautomaták által elfogadott nyelvek osztálya valódi részosztálya a nemdeterminisztikus veremautomaták által elfogadott nyelvek osztályának.

A determinisztikus veremautomaták által végállapottal elfogadott nyelvek osztályát determinisztikus környezetfüggetlen nyelveknek hívjuk.

A determinisztikus veremautomatákkal üres veremmel elfogadható nyelvek osztálya valódi része a végállapottal elfogadható nyelvek osztályának. A determinisztikus veremautomatákkal üres veremmel elfogadható nyelvek osztálya egy nagyon szűk nyelvosztály, hiszen az automatának determinisztikus módón ki kell ürítenie a vermet az adott szó elolvasásakor (után) anélkül, hogy tudná van-e még hátra az inputból.

Itt jegyezzük meg, hogy a lineáris (nyelvtanok által generált) nyelvek éppen az egyszerforduló veremautomaták által elfogadott nyelvek osztálya. Az egyszerforduló veremautomaták olyan speciális veremautomaták amelyek működésük közben előbb csak "töltik" a vermet, aztán pedig csak "ürítik". Az átmenetfüggvényük olyan, hogy ha volt már törlés a veremből (vagyis olyan átmenet, amikor a legfelső veremszimbólum helyére csak a λ került), akkor már nem tehetnek a verembe újabb szimbólumokat.

A lineáris nyelvtanok levezetési fáit tekintve éppen az történik, hogy a baloldali ágakon levő terminálisok elolvasása közben a főág (a nemterminálisok) bekerülnek a verembe, és ennek megfelelően, őket fordított sorrendben kiszedve olvassuk el a jobb oldali terminálisokat.

A determinisztikus egyfordulós veremautomaták által elfogadott nyelveket tekinthetjük egyféle determiniszikus lineáris nyelveknek (detLin). Ez a nyelvosztály viszont halmazelméletileg nem összemérhető a determinisztikus 2-fejű automaták által definiált 2detLin nyelvosztállyal a tartalmazási relációra nézve.

A palindromák nyelve 2detLin nyelv, de nem detLin (a veremautomata nem tudja mikor értünk a szó közepére, így determinisztikusan nem tud "fordulni"). Viszont az {a n b a n }∪{a 2n c a n } nyelv detLin, de nem 2detLin.

Egy veremautomatát számláló-automatának hívunk, ha a verem tartalma csak X * Z 0 lehet, ekkor a nem törölhető kezdő veremszimbólumon (a veremalja jelen) kívül csupán egyetlen veremszimbólum áll rendelkezésre. Tulajdonképpen a veremnek így csak kétféle szimbólum lehet a tetején: X ha a verem "nemüres", és Z 0, ha a verem "üres". Tulajdonképpen egy számlálónk van amely értéke tetszőleges természetes szám lehet, viszont az automatánk csak azt a két esetet tudja megkülönböztetni, hogy nulla vagy pozitív az érték. Az ilyen számlálóautomatával elfogadott nyelveket számlálónyelveknek hívjuk. Megmutatható, hogy pl. a palindrómák nyelve nem számlálónyelv, így teljesül a következő

54. Tétel. A számlálónyelvek osztálya a környezetfüggetlen nyelvek osztályának valódi része.

7.25. példa - Veremautomaták 1. feladat


Adjunk meg a G 2-es típusú grammatikához egy olyan veremautomatát, amely
G grammatika által generált nyelvet ismeri fel, majd mutassuk meg, hogy
az 10011 szót felismeri az automata!
G=({S,A,B},{0,1},S,H),ahol H szabályai:
S → SA, S → AB,

               A → BS, B → SA,

               A → 1, S → 1, B → 0.



Megoldás:
Egy olyan megoldást fogunk adni, amely a G nyelvtan által generált nyelv szavait
egyszerre fogadja el végállapottal és üres veremmel.
- A szalagábécé álljon a grammatika terminálisaiból,
- A veremábécé pedig tartalmazza a terminálisokat, a nemterminálisokat és a kezdő veremszimbólumot!
- A belső állapotok halmaza 3 elemből áll, melyből egy  kezdő- egy általános- és egy végállapot.
- Az átmenetfüggvény definiálása:
 - Kell egy olyan szabály, hogy a kezdő veremszimbólum fölé írja az S kezdőszimbólumot, és
 átviszi az automatát általános állapotba!
 - Kellenek olyan szabályok, hogy az automata a szalagról nem olvas,
 a verem tetejéről olvassa a H-beli szabályok bal oldalát, majd
 visszaírja fordított sorrendben a jobb oldalát!
 - Kellenek olyan szabályok, hogy a szalagról és a verem tetejéről ugyanazt olvassuk,
 majd nem írunk semmit a verem tetejére!
 PDA = ({q
            0
            , q
            1
            , q
            2},{0, 1}, {S, A, B, 0, 1,z
            0}, q
            0
            , z
            0
            , δ, {q
            2}).
 δ(q
            0
            , λ, z
            0)={(q
            1
            , Sz
            0)},
 
            δ(q
            1
            , λ, S)={(q
            1
            , SA), (q
            1
            , AB), (q
            1
            , 1)},
 
            δ(q
            1
            , λ, A)={(q
            1
            , BS), (q
            1
            , 1)},
 
            δ(q
            1
            , λ, B)=(q
            1
            , SA), (q
            1
            , 0)},
 
            δ(q
            1
            , 1, 1)={(q
            1
            , λ)},
 
            δ(q
            1
            , 0, 0)={(q
            1
            , λ)},
 
            δ(q
            1
            , λ, z
            0)={(q
            2
            , λ)}.
 A Cocke-Younger-Kasami algoritmusos fejezet 7.35. példa - Cocke-Younger-Kasami algoritmus 1. feladat 
 segítségével találhatunk a következő legbaloldalibb levezetésére az 10011 szónak:
 
 SSASAAABAA⇒1BAA⇒10AA⇒10BSA⇒100SA⇒1001A⇒10011.

 Ezt levezetést használva mutatjuk meg az automata miyen lépéseken át ismerheti fel az 10011 szót:

 Az automata müködése előtt a konfiguráció: (szalagon még hátra lévő inputrész, állapot, verem)

 (10011, q
            0
            , z
            0)
 

1. lépés: Írjuk a kezdő veremszimbólum felé S-t! Ezt megteheti az automata, mert (q 1 , Sz 0) ∈ δ(q 0 , λ, z 0).

(10011, q 1 , Sz 0)

2. lépés: Az automata a verem tetejét SA-ra cserélheti mivel (q 1 , SA)∈ δ(q 1 , λ, S). (Alkalmaztuk az S → SA szabályt.)

(10011, q 1 , SAz 0)

3. lépés: Az automata a verem tetejét SA-ra cserélheti mivel (q 1 , SA)∈ δ(q 1 , λ, S). (Alkalmazzuk az S → SA szabályt.)

(10011, q 1 , SAAz 0)

4. lépés: A verem tetején az S helyett egy B-t majd egy A-t rakhat, mivel (q 1, AB)∈ δ(q 1 , λ, S). (Alkalmazzuk az S → AB szabályt.)

(10011, q 1 , ABAAz 0)

5. lépés: A verem tetején lévő A-t 1-esre cserélheti, mert (q 1 , 1)∈ δ(q 1 , λ, A). (Alkalmazzuk az A → 1 szabályt.)

(10011, q 1 , 1BAAz 0)

6. lépés: A szalagról olvashat az automata és a veremből törölhet, mert (q 1 , λ)∈ δ(q 1 , 1 ,1).

(0011, q 1 , BAAz 0)

7. lépés: A verem tetején lévő B-t 0-ásra cserélheti az automata, mert (q 1 , 0)∈ δ(q 1 , λ, B). (Alkalmazzuk a B → 0 szabályt.)

(0011, q 1 , 0AAz 0)

8. lépés: A szalagról olvashat és a veremből törölhet az automata, mert (q 1 , λ)∈ δ(q 1 , 0, 0).

(011, q 1 , AAz 0)

9. lépés: A verem tetején az A helyett egy S-t majd egy B-t rakhat, mivel (q 1 , BS)∈ δ(q 1 ,λ,A). (Alkalmazzuk az A → BS szabályt.)

(011, q 1 , BSAz 0)

10. lépés: A verem tetején lévő B-t 0-ásra cserélheti az automata, mert (q 1 , 0)∈ δ(q 1 , λ, B). (Alkalmazzuk a B → 0 szabályt.)

(011, q 1 , 0SAz 0)

11. lépés: A szalagról olvashat és a veremből törölhet az automata, mert (q 1 , λ)∈ δ(q 1 , 0, 0).

(11, q 1 , SAz 0)

12. lépés: A verem tetején lévő S-t 1-esre cserélheti az automata, mert (q 1 , 1)∈ δ(q 1 , λ, S). (Alkalmazzuk az S → 1 szabályt.)

(11, q 1 , 1Az 0)

13. lépés: A szalagról olvashat és a veremből törölhet az automata, mert (q 1 , λ)∈ δ(q 1 , 1, 1).

(1, q 1 , Az 0)

14. lépés: A verem tetején lévő A-t 1-esre cserélheti az automata, mert (q 1 , 1)∈ δ(q 1 , λ, A). (Alkalmazzuk az A → 1 szabályt.)

(1, q 1 , 1z 0)

15. lépés: A szalagról olvashat és a veremből törölhet az automata, mert (q 1 , λ)∈ δ(q 1 , 1, 1).

(λ, q 1 , z 0)

16. lépés: Az automata átmehet végállapotba és kiürítheti a vermet, mert (q 2 ) ∈ δ(q 1 , λ, z 0)

(λ, q 2 , λ),

vagyis az automata üres veremmel és végállapottal felismerte az 10011 szót.


 II. megoldás:
 
 Mivel a nyelvtanunk (terminális) normálalakú, azaz terminális csak X → x szabályokban fordul elő,
 ahol XN és xT, ezért az átmenetfüggvény a következő lehet:
 - Kell egy olyan szabály, hogy a kezdő veremszimbólum fölé írja az S kezdőszimbólumot, és
 átviszi az automatát általános állapotba!
 - Kellenek olyan szabályok, hogy az automata a szalagról nem olvas,
 a verem tetejéről olvassa a H-beli szabályok bal oldalát, majd
 visszaírja a jobb oldalát, ha a jobboldal nem tartalmaz terminálist!
 - Kellenek olyan szabályok, hogy a szalagról x-et és a verem tetejéről X-et olvassuk,
 majd nem írunk semmit a verem tetejére, ha X → xH, és XN, xT!
 - És kell egy olyan szabály, hogy ha általános állapotban olvassa az automata a kezdő veremszimbólumot,
 akkor menjen át végállapotba!
 Ekkor a veremautomata:
 A({q
            0
            , q
            1
            , q
            2}, {0, 1}, {S, A, B, 0, 1,z
            0}, q
            0
            , z
            0
            , δ, {q
            2}).
 δ(q
            0
            , λ, z
            0)={(q
            1
            , Sz
            0)},
 
            δ(q
            1
            , λ, S)={(q
            1
            , SA),(q
            1
            , AB)}
 δ(q
            1
            , λ, A)={(q
            1
            , BS)},
 
            δ(q
            1
            , λ, B)={(q
            1
            , SA)},
 
            δ(q
            1
            , 1, A)={(q
            1
            , λ)},
 
            δ(q
            1
            , 1, S)={(q
            1
            , λ)},
 
            δ(q
            1
            , 0, B)={(q
            1
            , λ)},
 
            δ(q
            1
            , λ, z
            0)={(q
            2
            , λ)}.
 
 A második automata müködése:
 

(10011, q 0 , z 0)

1. lépés: Írjuk a kezdő veremszimbólum felé S-t! Ezt megteheti az automata, mert (q 1 , Sz 0) ∈ δ(q 0 , λ, z 0).

(10011, q 1 , Sz 0)

2. lépés: Az automata a verem tetejét kicserélheti SA-ra mivel (q 1 , SA)∈ δ(q 1 , λ, S). (Alkalmaztuk az S → SA szabályt.)

(10011, q 1 , SAz 0)

3. lépés: Az automata a verem tetejét kicserélheti SA-ra mivel (q 1 , SA)∈ δ(q 1 , λ, S). (Alkalmaztuk az S → SA szabályt.)

(10011, q 1 , SAAz 0)

4. lépés: Alkalmazzuk az S → AB szabályt! (q 1 , AB) ∈ δ(q 1 , λ, S).

(10011, q 1 , ABAAz 0)

5. lépés: A szalagról olvasunk, a veremből törlünk. (q 1 , λ) ∈ δ(q 1 , 1, A).

(0011, q 1 , BAAz 0)

6. lépés: A szalagról olvasunk, a veremből törlünk. (q 1 , λ) ∈ δ(q 1 , 0, B).

(011, q 1 , AAz 0)

7. lépés: (q 1 , BS) ∈ δ(q 1 , λ, A). (Alkalmazzuk az A → BS szabályt.)

(011, q 1 , BSAz 0)

8. lépés: A szalagról olvasunk, a veremből törlünk. (q 1 , λ) ∈ δ(q 1 , 0, B).

(11, q 1 , SAz 0)

9. lépés: A szalagról olvasunk, a veremből törlünk. (q 1 , λ) ∈ δ(q 1 , 1, S).

(1, q 1 , Az 0)

10. lépés: A szalagról olvasunk, a veremből törlünk. (q 1 , λ) ∈ δ(q 1 , 1, A).

(λ, q 1 , z 0)

11. lépés: (q 2 ) ∈ δ(q 1 , λ, z 0)

(λ, q 2 , λ),

vagyis az automata üres veremmel és végállapottal felismerte az 10011 szót. ★

7.26. példa - Veremautomaták 2. feladat



Adjunk meg olyan veremautomatát, amely pontosan a következő grammatika által generált nyelv szavait
ismeri fel, és mutassuk meg, hogy a bbcbba szót is elfogadja!
 G=({S,A,B,C,D},{a,b,c},S,H), ahol H szabályai:
 S → AB, A → CA, A → SS, B → CD,
 
            A → b, D → a, C → c, C → b.
 Megoldás:
 A({q
            0
            , q
            1
            , q
            2}, {a, b, c}, {S, A, B, C, D, a, b, c, z
            0}, q
            0
            , z
            0
            , δ, {q
            2}).
 (q
            1
            , Sz
            0) ∈ δ(q
            0
            , λ, z
            0),
 (q
            1
            , AB) ∈ δ(q
            1
            , λ, S),
 (q
            1
            , CA) ∈ δ(q
            1
            , λ, A),
(q
            1
            , SS) ∈ δ(q
            1
            , λ, A),
(q
            1
            , CD) ∈ δ(q
            1
            , λ, B),
(q
            1
            , b) ∈ δ(q
            1
            , λ, A),
(q
            1
            , a) ∈ δ(q
            1
            , λ, D),
(q
            1
            , c) ∈ δ(q
            1
            , λ, C),
(q
            1
            , b) ∈ δ(q
            1
            , λ, C),
(q
            1
            , λ) ∈ δ(q
            1
            , a, a),
(q
            1
            , λ) ∈ δ(q
            1
            , b, b),
(q
            1
            , λ) ∈ δ(q
            1
            , c, c),
(q
            2
            , λ) ∈ δ(q
            1
            , λ, z
            0). Az egyetlen legbaloldalibb levezetés (pl. a Cocke-Younger-Kasami algoritmusos fejezet
 7.37. példa - Cocke-Younger-Kasami algoritmus 3. feladat alapján):
 SABCABbABbCABbbABbbCABbbcABbbcbBbbcbCDbbcbbDbbcbba
A szó felismerésének lépései:
 (bbcbba,q
            0
            ,z
            0)
 
 1. lépés (q
            1
            , Sz
            0) ∈ δ(q
            0
            , λ, z
            0
 (bbcbba,q
            1
            , Sz
            0)
 
 2. lépés (q
            1
            , AB) ∈ δ(q
            1
            , λ, S
 (bbcbba,q
            1
            , ABz
            0)
 
 3. lépés (q
            1
            , CA) ∈ δ(q
            1
            , λ, A
 (bbcbba,q
            1
            , CABz
            0)
 
 4. lépés (q
            1
            , b) ∈ δ(q
            1
            , λ, C
 (bbcbba,q
            1
            , bABz
            0)
 
 5. lépés (q
            1
            , λ) ∈ δ(q
            1
            , b, b
 (bcbba,q
            1
            , ABz
            0)
 
 6. lépés (q
            1
            , CA) ∈ δ(q
            1
            , λ, A
 (bcbba,q
            1
            , CABz
            0)
 
 7. lépés (q
            1
            , b) ∈ δ(q
            1
            , λ, C
 (bcbba,q
            1
            , bABz
            0)
 
 8. lépés (q
            1
            , λ) ∈ δ(q
            1
            , b, b
 (cbba,q
            1
            , ABz
            0)
 
 9. lépés (q
            1
            , CA) ∈ δ(q
            1
            , λ, A
 (cbba,q
            1
            , CABz
            0)
 
 10. lépés (q
            1
            , c) ∈ δ(q
            1
            , λ, C
 (cbba,q
            1
            , cABz
            0)
 
 11. lépés (q
            1
            , λ) ∈ δ(q
            1
            , c, c
 (bba,q
            1
            , ABz
            0)
 
 12. lépés (q
            1
            , b) ∈ δ(q
            1
            , λ, A
 (bba,q
            1
            , bBz
            0)
 
 13. lépés (q
            1
            , λ) ∈ δ(q
            1
            , b, b
 (ba,q
            1
            , Bz
            0)
 
 14. lépés (q
            1
            , CD) ∈ δ(q
            1
            , λ, B
 (ba,q
            1
            , CDz
            0)
 
 15. lépés (q
            1
            , b) ∈ δ(q
            1
            , λ, C
 (ba,q
            1
            , bDz
            0)
 
 16. lépés (q
            1
            , λ) ∈ δ(q
            1
            , b, b
 (a,q
            1
            , Dz
            0)
 
 17. lépés (q
            1
            , a) ∈ δ(q
            1
            , λ, D
 (a,q
            1
            , az
            0)
 
 18. lépés (q
            1
            , λ) ∈ δ(q
            1
            , a, a
 (λ ,q
            1
            , z
            0)
 
 19. lépés (q
            2
            , λ) ∈ δ(q
            1
            , λ, z
            0
 (λ, ,q
            2
            , λ)        
 
 Tehát az automata végállapottal és üres veremmel felismerte a szót! ★
 

7.27. példa - Veremautomaták 3. feladat


Adjunk meg olyan veremautomatát, mely pontosan a G grammatika által generált nyelv szavait ismeri fel!
G=({S, A, B},{x, y}, S, H), ahol H a következő szabályokból áll:
S → AB, A → BSB, A → BB, B → xAy,
B → λ, B → x, B → y.
Megoldás:
A({q
               0
               , q
               1
               , q
               2}, {x, y}, {S, A, B, x, y, z
               0}, q
               0
               , z
               0
               , δ, {q
               2}).
 (q
               1
               , Sz
               0) ∈ δ(λ, q
               0
               , z
               0),
 (q
               1
               , AB) ∈ δ(λ, q
               1
               , S),
 (q
               1
               , BSB) ∈ δ(λ, q
               1
               , A),
 (q
               1
               , BB) ∈ δ(λ, q
               1
               , A),
 (q
               1
               , xAy) ∈ δ(λ, q
               1
               , B),
 (q
               1
               , λ) ∈ δ(λ, q
               1
               , B),
 (q
               1
               , x) ∈ δ(λ, q
               1
               , B),
 (q
               1
               , y) ∈ δ(λ, q
               1
               , B),
 (q
               1
               , λ) ∈ δ(x, q
               1
               , x),
 (q
               1
               , λ) ∈ δ(y, q
               1
               , y),
 (q
               2
               , λ) ∈ δ(λ, q
               1
               , z
               0). ★
 


7.28. példa - Veremautomaták 4. feladat


Készítsünk olyan veremautomatát, amely az L={anbn
               
n ≥ 0}  nyelvet ismeri fel!
 


Megoldás: 
- Mivel az üresszó eleme L-nek, az automata q
               0 kezdőállapota egyben egy végállapot is.
- Ha olvasunk egy a betűt, akkor írunk a verembe egy a-t, és átmegyünk a q
               1 állapotba.
- Ha olvasunk egy a-t akkor a verem tetejére rakunk még egy a-t, és maradunk ebben az állapotban.
- Ha b-t olvasunk, akkor kiveszünk egy a-t a veremból, majd átmegyünk a q
               2 állapotba.
- Ha b-t olvasunk a szalagon és a-t a veremben, akkor maradunk itt, és kiveszünk egy a-t.
- Ha z
               0-t olvasunk a veremből és nincs betű a szalagon,
akkor ürítjük a vermet, és átmegyünk q
               3 állapotba, mely szintén végállapot.
Az elkészült automatát a következő ábra mutatja:
 


Itt jegyezzük meg, hogy az L nyelv egy számlálónyelv. Ha a fenti megoldásban az utolsó lépésben nem töröljük ki a z 0-t a veremből, úgy megyünk át a q 3 elfogadóállapotba, akkor az elkészített automatánk számláló-automata. ★

7.29. példa - Veremautomaták 5. feladat


Készítsünk olyan veremautomatát, amely az L={anbm
               
| 0 ≤ n ≤ m ≤ 2n}  nyelvet ismeri fel!
 


Megoldás: 
- Mivel az üresszó eleme L-nek, az automata q
               0 kezdőállapota egyben egy végállapot is.
- Ha olvasunk egy a betűt, akkor írunk a verembe egy a-t vagy két a-t, és átmegyünk a q
               1 állapotba.
- Ha olvasunk egy a-t akkor a verem tetejére rakunk még egy a-t vagy két a-t, és maradunk ebben az állapotban.
- Ha b-t olvasunk, akkor kiveszünk egy a-t a veremból, majd átmegyünk a q
               2 állapotba.
- Ha b-t olvasunk a szalagon és a-t a veremben, akkor maradunk itt, és kiveszünk egy a-t.
- Ha z
               0-t olvasunk a veremből és nincs betű a szalagon,
akkor ürítjük a vermet, és átmegyünk q
               3 állapotba, mely szintén végállapot. A kész automata:
 


Gyakorló feladatként bizonyítsuk be, hogy az L nyelv egy számlálónyelv, vagyis készítsünk egy L-et elfogadó számláló-automatát. ★

7.30. példa - Veremautomaták 6. feladat


Készítsünk olyan veremautomatát, amely az L={w | |w|a = |w|b
               
}  nyelvet ismeri fel!
(Azok a szavak az {a,b} ábécé felett, melyekben az a-k és a b-k száma megegyezik.)
 


Megoldás:
A veremben csak legfeljebb egyféle z
               0-tól eltérő szimbólum lehet.
- csak z
               0 van: ugyanannyi a és b betű került elolvasásra eddig.
k db a betű van a z
               0 felett, akkor eddig k-val több a-t olvastunk be.
k db b betű van a z
               0 felett, akkor eddig k-val több b-t olvastunk be.

az automata működése:
- Ha a veremben csak z
               0 van, akkor a szalagról olvasott jelet tegyük a verem tetejére.
- Ha a verem tetején lévő és a beolvasott jel egyforma, akkor ezek számát a veremben növeljük 1-gyel.            
- Ha a verem tetején lévő és a beolvasott jel eltérő, akkor a veremben lévők számát csökkentjük 1-gyel.
- Ha a veremben csak z
               0 van, akkor kiüríthetjük a vermet, és átmehetünk vágállapotba.
 


7.31. példa - Veremautomaták 7. feladat


Készítsünk olyan veremautomatát, amely az L={aibjck
               
i,j,k ≥ 0 és i=j vagy i=k}  nyelvet ismeri fel!
 


Megoldás:
Fontos, hogy az automatánk nemdeterminisztikus.
- Az egyik "ág" (q
               0
               ,q
               1
               ,q
               2
               ,q
               4) azokat a szavakat ismeri fel, mikor az a-k és a b-k száma egyforma.
- A másik "ág" (q
               0
               ,q
               1
               ,q
               3
               ,q
               5
               ,q
               6) azokat a szavakat ismeri fel, mikor az a-k és a c-k száma egyforma.
- Arra kell még figyelni, hogy a*b*c*
               
 alakú legyen a szó és lehet ijk=0 (i,j,k közül bármelyik,
 vagy több is lehet 0) is.
- Az automata végállapottal ismer fel.            
 


7.32. példa - Veremautomaták 8. feladat


Készítsünk olyan veremautomatát, amely L={wcw
               -1w∈{a,b}*w
               -1 a w fordítottja} nyelvet ismeri fel,
 


Megoldás:
- Ha c-t olvasunk, akkor rögtön kiürítjük a vermet, és átmegyünk végállapotba.
- Ha a-t vagy b-t olvasunk, átmegyünk egy másik állapotba (töltő állapotba), és berakjuk a verembe,
 amit olvasunk.
- Ha töltő állapotban a-t vagy b-t olvasunk, akkor az megy a verembe.
- Ha c-t olvasunk, akkor a vermet változatlanul hagyjuk, és újabb állapotba megyünk (kiürítő állapot).
- Ha kiürítő állapotban a verem tetején lévő betű megegyezik az olvasottal, akkor azt kivesszük a veremből.
- Ha z
               0-t elérjük, akkor kiürítjük a vermet, és átmegyünk végállapotba.

 


7.33. példa - Veremautomaták 9. feladat


Készítsünk olyan üres veremmel elfogadó veremautomatát, amely az {a,b} ábécé fölötti helyes
zárójelszavak nyelvét, ahol a a nyitó, b pedig a záró zárójel (vagyis a Dyck nyelvet) ismeri fel!
 


Megoldás:
- Ha a-betűt olvasunk a szalagon, akkor a verembe írjuk.
- Ha b-t olvasunk a szalagon, törlünk egy a-t.
- Ha z
               0-t olvasunk, akkor kiüríthetjük a vermet, vagy folytathatjuk a olvasásával is.