Formális nyelvek gyakorlat (plusz)

2005. december 15., csütörtök



1. Legyen a nyelvtanunk a következő: $P\ensuremath{\rightarrow}bDSe$, $D\ensuremath{\rightarrow}dvD\;\vert\;dv$, $S\ensuremath{\rightarrow}uvS\;\vert\;uv$. Elemezzük az Earley algoritmussal a $bdvuvuve$ szót!

2. A nyelvtan az $S\ensuremath{\rightarrow}SaSaS\;\vert\;\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 &\ensuremath{\rightarrow}& AB, \\ A &\ensuremath{\rightarrow}& aAb \mid ab, \\ B &\ensuremath{\rightarrow}& bBc \mid bc \end{eqnarray*}$$

6. A CYK algoritmussal (elemzéssel) elemezzük 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ö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!