Az $S\ensuremath{\rightarrow}XY$, $X\ensuremath{\rightarrow}aXb\;\vert\;ab$, $Y\ensuremath{\rightarrow}bYc\;\vert\;bc$ nyelvtanhoz készítsünk PDA-t, mindkét konstrukcióval, amit tanultunk (vagy tanulni fogunk)! Elemezzük az $a^2b^5c^3$ szót mindkét automatával! Megoldás 1. konstrukció: A veremautomata kezdõállapota és egyben egyetlen állapota a $q$. Inputábécéje megegyzeik a nyelvtan terminálisaival, azaz $\{a,b,c\}$, veremábécéje a nyelvtan terminálisait és nemterminálisait tartalmazza, meg a $Z_0$-t: $\{a,b,c,S,X,Y,Z_0\}$. Üres veremmel fogad el, a szabályok: $\delta(q,\epsilon ,Z_0)=(q,S)$, azaz a veremalja jelet $S$-re cseréljük $\delta(q,a,a)=(q,\epsilon)$, $\delta(q,b,b)=(q,\epsilon)$, $\delta(q,c,c)=(q,\epsilon)$, azaz a terminálisokat ki tudja venni a verem tetejérõl, ha az inputon is ott állnak $\delta(q,\epsilon,S)=(q,XY)$, $\delta(q,\epsilon,X)=(q,aXb)\;\vert\;(q,ab)$, $\delta(q,\epsilon,Y)=(q,bYc)\;\vert\;(q,bc)$ azaz, ha egy nemterminális van a verem tetején, akkor azt helyettesítheti egy neki megfelelõ jobboldallal (a nyelvtan szerint megfelelõvel). Az elemzés úgy megy, hogy a veremben szimuláljuk a levezetéseket és ha olyan terminális jön ki elõre, ami az inputon is van, akkor kivesszük a terminálist a verembõl. A verem pontosan akkor ürül ki, mire elfogy az input, ha van levezetése a szónak, azaz ha eleme a nyelvnek. Elemzés (elöl az állapot, aztán a veremtartalom, aztán az input még olvasatlan része): $(q, Z_0, aabbbc)\ensuremath{\rightarrow}$ $(q, S, aabbbc)\ensuremath{\rightarrow}$ $(q, XY, aabbbc)\ensuremath{\rightarrow}$ $(q, aXbY, aabbbc)\ensuremath{\rightarrow}$ $(q, XbY, abbbc)\ensuremath{\rightarrow}$ $(q, abbY, abbbc){\ensuremath{\rightarrow}}^+$ $(q, Y, bc)\ensuremath{\rightarrow}$ $(q, bc, bc){\ensuremath{\rightarrow}}^+$ $(q, \epsilon, \epsilon)$ Megjegyzések: 1. Ahol terminálisokat olvastunk csak ki a verembõl, ott több lépést is összevontam. 2. Ha nem pont ezeket a szabályokat használtam volna, akkor nem ürült volna ki a verem, azon az úton nem fogadtuk volna el a szót. De ez nem baj, ez egy nemdeterminisztikus veremautomata, akkor fogad el egy szót, ha van olyan mûködése, ami során elfogad. 3. Ha beszámozzuk a szabályokat a nyelvtanban ( $S\ensuremath{\rightarrow}XY, 1$, stb.) és a veremautomata mûködése során mindig felírjuk, hogy melyik nyelvtani szabálynak megfelelõ szabályt használtuk az elemzés során, akkor az így kiírt számsor éppen a szó (egyik, ha több is van) ballevezetését kódolja. (Itt 1235) 2. konstrukció A veremautomata egy röntgenszemû automata lesz. A kezdõállapota és egyben egyetlen állapota a $q$. Inputábécéje megegyezik most is a nyelvtan terminálisaival, azaz $\{a,b,c\}$, veremábécéje a nyelvtan terminálisait és nemterminálisait tartalmazza, meg a $Z_0$-t: $\{a,b,c,S,X,Y,Z_0\}$. Üres veremmel fogad el, a szabályok: $\delta(q,\epsilon ,SZ_0)=(q,\epsilon)$, azaz ha már csak az $S$ van a veremben a veremalja jel felett, akkor kiürítjük a vermet $\delta(q,a,A)=(q,aA)$, $\delta(q,b,A)=(q,bA)$, $\delta(q,c,A)=(q,cA)$, ahol $A$ tetszõleges veremszimbólum azaz a terminálisokat be tudja tenni a verembe bármikor $\delta(q,\epsilon,YX)=(q,S)$, $\delta(q,\epsilon,bXa)=(q,X)$ $\delta(q,\epsilon,ba)=(q,X)$ $\delta(q,\epsilon,cYb)=(q,Y)$ $\delta(q,\epsilon,cb)=(q,Y)$ azaz, ha a verem tetején megjelenik egy nyelvtani szabály jobboldalának a fordítottja, akkor ahelyett be lehet írni a szabály baloldalát Az elemzés úgy megy, hogy a verembe pakoljuk a terminálisokat, addig amíg valami nyelvtani szabály jobboldalának fordítottja nem lesz felül, ekkor letörünk, azaz a jobboldal helyett a baloldalon álló nemterminálist rakjuk be. A verem itt is pontosan akkor ürül ki, mire elfogy az input, ha van levezetése a szónak, azaz ha eleme a nyelvnek. Elemzés (elöl az állapot, aztán a veremtartalom, aztán az input még olvasatlan része): $(q, Z_0, aabbbc){\ensuremath{\rightarrow}}^*$ $(q, baaZ_0, bbc)\ensuremath{\rightarrow}$ $(q, XaZ_0, bbc)\ensuremath{\rightarrow}$ $(q, bXaZ_0, bc)\ensuremath{\rightarrow}$ $(q, XZ_0, bc){\ensuremath{\rightarrow}}^*$ $(q, cbXZ_0, \epsilon)\ensuremath{\rightarrow}$ $(q, YXZ_0, \epsilon)\ensuremath{\rightarrow}$ $(q, SZ_0, \epsilon)\ensuremath{\rightarrow}$ $(q, \epsilon, \epsilon)\ensuremath{\rightarrow}$ Megjegyzések: 1. Ahol terminálisokat írunk be a verembe, ott több lépést is összevontam. 2. Ha nem pont ezeket a szabályokat használtam volna, akkor nem ürült volna ki a verem, de ez itt se baj. 3. Ha beszámozzuk a szabályokat a nyelvtanban ( $S\ensuremath{\rightarrow}XY, 1$, stb.) és a veremautomata mûködése során mindig felírjuk, hogy melyik nyelvtani szabálynak megfelelõ szabály szerint törtünk le az elemzés során, akkor az így kiírt számsor éppen a szó (egyik, ha több is van) jobblevezetését kódolja fordítva. (Itt 3251)