

\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\newcommand{\ra}{\ensuremath{\rightarrow}}


\setlength{\textheight}{26cm}

\setlength{\textwidth}{16cm}

\setlength{\baselineskip}{13pt}

\setlength{\topmargin}{-1cm}

\setlength{\oddsidemargin}{0.4cm}

\setlength{\evensidemargin}{0.4cm}

\pagestyle{empty}

\begin{document}
\ \ \\ \ \ \\
\noindent
Az $S\ra XY$, $X\ra aXb\;|\;ab$, $Y\ra bYc\;|\;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!
\\
\ \ \\
{\bf 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)\;|\;(q,ab)$,
$\delta(q,\epsilon,Y)=(q,bYc)\;|\;(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)\ra $\\
$(q, S, aabbbc)\ra $\\
$(q, XY, aabbbc)\ra $\\
$(q, aXbY, aabbbc)\ra $\\
$(q, XbY, abbbc)\ra $\\
$(q, abbY, abbbc){\ra}^+ $\\
$(q, Y, bc)\ra $\\
$(q, bc, bc){\ra}^+ $\\
$(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\ra 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){\ra}^* $\\
$(q, baaZ_0, bbc)\ra $\\
$(q, XaZ_0, bbc)\ra $\\
$(q, bXaZ_0, bc)\ra $\\
$(q, XZ_0, bc){\ra}^* $\\
$(q, cbXZ_0, \epsilon)\ra $\\
$(q, YXZ_0, \epsilon)\ra $\\
$(q, SZ_0, \epsilon)\ra $\\
$(q, \epsilon, \epsilon)\ra $\\
\ \ \\
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\ra 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)   
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
