\documentclass[12pt]{article}

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


\setlength{\textheight}{26cm}

\setlength{\textwidth}{16cm}

\setlength{\baselineskip}{13pt}

\setlength{\topmargin}{-1.5cm}

\setlength{\oddsidemargin}{0.4cm}

\setlength{\evensidemargin}{0.4cm}

\pagestyle{empty}

\begin{document}
\noindent
{\large{\bf Formális nyelvek gyakorlat (10-11)}}
\\
\ \ 
\\
{\bf 2005. november 24. és december 1., csütörtök}
\vspace*{1cm}
\noindent
\\
1. Egy CF nyelvet az $S\ra SaSb\;|\;\epsilon$ nyelvtan definiál.\\ 
Készíts erre a nyelvre (erős) $LL(k)$ elemzőt minél kisebb $k$-val! 
Ezután elemezd az $aababb$ szót! 
\\
\ \ 
\\
2. Nézzük az $S\ra aAaa\;|\;bAba$, $A\ra b\;|\;\epsilon$  nyelvtant.
\\
(a) Igaz-e, hogy ez a {\bf nyelvtan} erős $LL(2)$ nyelvtan?
\\
(b) Készítsünk a nyelvtanhoz gyenge $LL(2)$ elemzőt!
\\
(c) Mutassuk meg, hogy ez nem gyenge $LL(1)$ nyelvtan!
\\  
\ \ 
\\
3. Egy CF nyelvet az $S\ra SaSab\;|\;\epsilon$ nyelvtan definiál.\\ 
(a) Készíts erre a nyelvre gyenge $LL(k)$ elemzőt minél kisebb $k$-val! 
\\
(b) Ezután elemezd az $aaababaab$ szót! 
\\
(c) Készíts az (a)-ban adott gyenge elemzőből erőset,
aztán nézd meg, hogy hogyan viselkedik a gyenge és az erős az 
$aabab$ szón! 
\\
\ \ 
\\
{\bf Aki gondolkodni is akar, nem csak számolni:}
\\
\ \ 
\\
4. Gondoljuk meg, hogy 
\\ 
(a) mit jelent az, hogy egy nyelvtan $LL(0)$ tulajdonságú?\\ 
(b) miért nem $LL(k)$ elemezhető egy balrekurzív nyelvtan?
\\
(c) miért biztos az, hogy egy nemegyértelmű nyelvtan nem $LL(k)$ 
elemezhető?
\\
(d) van-e olyan $L$ nyelv és olyan $k$ szám, hogy $L$-re csak gyenge 
$LL(k)$ elemző készíthető, erős nem?
\\
\ \ 
\\
{\bf Gyakorolni}
\\
\ \ 
\\
5. {\bf Egyszerű}\\
 a) Készíts $LL(1)$ elemzőtáblát az alábbi egyszerű szintaxisvezérelt 
fordítási séma első nyelvtanához, 
\\ 
b) elemezd segítségével az $aabbbb$ jelsorozatot, \\ 
c) és állítsd elő a mondat fordítását! 
 
\begin{tabbing} 
$S\ra aAbb,$\hspace*{2cm}\=$aA$\\ 
$A\ra S$,\>$Sbb$\\ 
$A\ra \epsilon$,\>$bb$ 
\end{tabbing}   
6. {\bf Bonyolultabb}
\\
Készíts $LL(k)$ elemzőt az $E\ra EE+\;|\;EE*\;|\;a$ nyelvtan  
által generált nyelvre minél kisebb $k$-val! A lokális FOLLOW függvények 
alapján történő felhasítással biztosítsd a legrészletesbb hibajelzést! 
Vizsgáld meg, hogy  az elemző elkészítésére használt nyelvtan erős 
$LL(k)$ nyelvtan-e (azzal a $k$-val, amivel gyenge)! 
Ha erős, akkor hasonlítsd össze az erős és a gyenge elemzőt és keress 
olyan jelsorozatot amin a két elemző máshogy működik! 

\end{document}








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












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

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

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

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