\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 (plusz)}}
\\
\ \ 
\\
{\bf 2005. december 15., csütörtök}
\vspace*{1cm}
\noindent
\\
1. Legyen a nyelvtanunk a következő: $P\ra bDSe$, $D\ra dvD\;|\;dv$, 
$S\ra uvS\;|\;uv$. Elemezzük az Earley algoritmussal a $bdvuvuve$ szót!
\\  
\ \ 
\\
2. A nyelvtan az $S\ra SaSaS\;|\;\epsilon$, elemezd az $aa$ szót az
Earley algoritmussal és jelöld be, hogy az elemek közül melyeket
használja ténylegesen az elemző!
\\ \ \ \\
3. A bemeneti és a kimeneti ábécé is $\{0,1,\$\}$. A kimenet és a
bemenet is egy természetes szám olyan bináris reprezentációja, melynél
az első karakter jelöli a legkisebb helyiértékű bitet, az utolsó
karakter pedig $\$$. Véges fordító kell, ami a bemenet háromszorosát
állítja elő.
\\ \ \ \\
4. A bemeneti ábécé $\{a,b\}$, a fordítandó nyelvben azon sorozatok
vannak, melyekben minden teljes homogén $a$-sorozat páros, minden
teljes homogén $b$-sorozat pedig páratlan hosszú.
A véges fordító az első beolvasott karakter után nem ad ki semmit, a
másodiktól kezdve pedig $x$-et ír, ha a karakter megegyezik az
előzővel és $y$-t, ha nem. Készítsünk két automatát:az első azon szavakat
fogadja el, amik előállnak fordításként (vagyis amiknek van olyan
eredetije, ami benne van a fordítandó nyelvben); 
a második azon szavakat fogadja el, amiknek az eredetije biztos benne 
volt a fordítandó nyelvben.   
\\ \ \ \\
5. A Coke--Younger--Kasami módszer segítségével  határozzuk meg
az $aabbbc$ szó összes jobboldali levezetését, ha a nyelvtan
a következő:
\begin{eqnarray*}
S &\ra& AB, \\
A &\ra& aAb \mid ab, \\
B &\ra& bBc \mid bc
\end{eqnarray*}
\\
\ \ 
\\
6. A CYK algoritmussal (elemzéssel) elemezzük az $E\ra E+E\;|\;E*E\;|\;a$ nyelvtanban az\\
(a) $a+a*a+a$ szót\\
(b) $a++a$ szót! 
\\
Döntsük el, hogy generálhatók-e a nyelvtannal, egyértelműen generálhatók-e és 
adjuk meg a levezetési fákat is!
\\
\ \ 
\\
\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: 
