Fordításelmélet

Formális nyelvek gyakorlat (9)

1999. április 13., kedd

1. Adjatok véges fordítót, ami az alábbi dolgot teszi: bemenetként $\{a,b\}$ feletti szavakat vesz és átírja őket $\{c,d\}$ feletti szavakká, úgy, hogy az a-t c-re, a b-t meg d-re cseréli. (Nagyon egyszerű!)

2. Véges fordító kell megint: bemenő ábécé az $\{a,b\}$ és a fordító ezt tegye: ha az utoljára olvasott karakter megegyezik az azelőttivel, akkor írjon x-et, ha különböznek, akkor írjon y-t. Az első karakter beolvasása után ne írjon semmit, így egy n hosszú szöveg fordítása n-1 hosszú lesz.

3. Az előbbi fordítóval lefordítjuk azt a nyelvet, mely azon szavakból áll, ahol a szavakban a karakterek száma páratlan. Mi lesz a fordított nyelv automatája?

4. HÁZI FELADAT, BEADANDÓ
A fordító ugyanaz, mint fent. A fordítandó nyelv: a szavak a-val kezdődnek, b-vel végződnek és a páros hosszú b-sorozatok száma páratlan. A fordított nyelvre kell automata.

5. Gondolkodni!!!
A fordító ugyanaz, mint fentebb. A fordítandó nyelv a nem szájbarágós palindróma, azaz:
$\{ww^{-1}\;\vert\;w\in{\{a,b\}}^*\}$. Nyelvtan kell a fordítottra.

6. Készítsünk szigorúan jellemző nyelvtant az 1. feladatban leírt fordításhoz.

7. Bizonyítsuk be:
Ha egy fordításhoz van jellemző nyelvtan, akkor van hozzá szigorúan jellemző nyelvtan is.

8. 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) HF 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!

9. Gyakorolni
A CYK elemzéssel elemezzük az $S\ensuremath{\rightarrow} aSa\;\vert\;bSb\;\vert\;aa\;\vert\;bb$ nyelvtanban az abbbba és az abbba szót!