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ű!) Megoldás 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. Megoldás 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? Megoldás 4. 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. Megoldás 5. 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. Megoldás 6. Készítsünk szigorúan jellemző nyelvtant az 1. feladatban leírt fordításhoz. Megoldás 7. Bizonyítsuk be: Ha egy fordításhoz van jellemző nyelvtan, akkor van hozzá szigorúan jellemző nyelvtan is. (A megoldás benne van a jegyzetben) 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! Megoldás 9. 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! Megoldás