Formális nyelvek gyakorlat (11) 2001., április 24., kedd 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\ensuremath{\rightarrow}E+E\;\vert\;E*E\;\vert\;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 &\ensuremath{\rightarrow}& AB, \\ A &\ensuremath{\rightarrow}& aAb \mid ab, \\ B &\ensuremath{\rightarrow}& bBc \mid bc \end{eqnarray*}$$ Megoldás Gyakorolni 4. A CYK algoritmussal (elemzéssel) elemezd az $E\ensuremath{\rightarrow}E+E\;\vert\;E*E\;\vert\;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! Megoldás 5. Már megint az Earley algoritmus: a nyelvtan az $S\ensuremath{\rightarrow}SaSb\;\vert\;\epsilon$. Az elemzendõ szó: $aababbab$. Segítség: az $S\ensuremath{\rightarrow}\epsilon$ szabály az olyan, hogy amint elkezdõdik, rögtön be is fejezõdik. Megoldás Ezt az elõadáson végigszámoltuk 6. Legyen a nyelvtanunk a következõ: $P\ensuremath{\rightarrow}bDSe$, $D\ensuremath{\rightarrow}dvD\;\vert\;dv$, $S\ensuremath{\rightarrow}uvS\;\vert\;uv$. Elemezd az Earley algoritmussal a $bdvuvuve$ szót! Megoldás