\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 (11)}}
\\
\ \ 
\\
{\bf 2001., április 24., kedd}
\\
\ \ \\
\noindent
1. Adj jellemző nyelvtant ahhoz a fordításhoz, ami az $\{a,b\}$ ábécé feletti
páros sok $b$-t tartalmazó szavakat fordítja le, mégpedig úgy, hogy 
ha a fordítandó szóban $2k$ darab $b$ van, akkor a kimenet a $k$ darab $d$ 
betűből álló szó.
\\
\ \ \\
2. Earley algoritmussal elemezd az $a+a*a$ szót az $E\ra E+E\;|\;E*E\;|\;a$
nyelvtanban. 
Ne felejtsd el visszakeresni a levezetési fát!
Gondold végig, hogy hol látszik az elemzésben az, hogy nem 
egyértelmű a nyelvtan!
\\
\ \ \\
3. A Coke--Younger--Kasami módszer segítségével  határozd meg
az $aabbbc$ szó összes levezetési fáját, ha a nyelvtan
a következő:
\begin{eqnarray*}
S &\ra& AB, \\
A &\ra& aAb \mid ab, \\
B &\ra& bBc \mid bc
\end{eqnarray*}
\\
\ \ \\
{\bf Gyakorolni}
\\
\ \ \\
4. A CYK algoritmussal (elemzéssel) elemezd az $E\ra E+E\;|\;E*E\;|\;a$ nyelvtanban az\\
(a) $a+a*a+a$ szót\\
(b) $a++a$ szót! 
\\
Döntsd el, hogy generálhatók-e a nyelvtannal, egyértelműen generálhatók-e és 
add meg a levezetési fákat is!
\\
\ \ \\
5. Már megint az Earley algoritmus: a nyelvtan az $S\ra SaSb\;|\;\epsilon$.
Az elemzendő szó: $aababbab$.
\\ Segítség: az $S\ra \epsilon$ szabály az olyan, hogy amint elkezdődik, 
rögtön be is fejeződik.
\\ \
\ \ \\
{\bf Ezt az előadáson végigszámoltuk}
\\
\ \ \\
6. Legyen a nyelvtanunk a következő: $P\ra bDSe$, $D\ra dvD\;|\;dv$, 
$S\ra uvS\;|\;uv$. Elemezd az Earley algoritmussal a $bdvuvuve$ szót!
\\  
\ \ 
\\



\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
%%% End: 

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

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