Sziasztok! A mai óra anyaga: 1. Determinisztikus CF nyelvek. Egy nyelv akkor det CF, ha van hozzá determinisztikus veremeautomata, ami õt fogadja el. Vigyázat! Nem determinisztikus CF nyelvtan (bármit is jelentsen az, hogy det CF nyelvtan). Még vigyázat: a det PDA-ban nem csak az kell, hogy ne legyen két olyan szabály, ahol mindkettõben ugyanaz az (állapot, olvasott szimbólum, veremtetõ) vagy (állapot, epszilon, veremtetõ) hármas áll a baloldalon, hanem annak is teljesülnie kell, hogy ha van szabály vmi (állapot, epszilon , veremtetõ) esetre, akkor ezt semmilyen olvasott szimbólummal kiegészítve sincs szabály a PDA-ban. Megbeszéltük, hogy a CF nyelvek nem zártak a metszetre és a komplementerképzésre, de zártak az unióra, viszont a det CF-ek meg nem zártak a metszetre és az únióra, de zártak a komplementerre. (Bizonyítás elõadáson, illetve a jegyzetben.) 2. Véges fordító: definíció, reguláris nyelvek zártak a véges fordításra (Bizonyítás volt egy példán keresztül, megnéztük a 3. feladatot. Beadható, hasonlóan menõ feladat a 6.(Megjegyzés: nem mindig érdemes a tanult konstrukciót használni, néha a józan ész többet ér.)), CF nyelvek is zártak a véges fordításra (Ez csak kimondva szerepelt, biz nélkül, a biz majd elõadáson.) Veremfordító: definíció 3. Szintaxis vezérelt fordítási séma (SZFS) és egyszerû szintaxis vezérelt fordítási séma (ESZFS). Ez utóbbi egyenértékû a veremfordítással. (Biz majd az elõadáson.) Feladatok közül a 4. és 5. majd csak következõ órán lesz, a többi már most volt, részben megbeszélve. Fordításelmélet 0. Mi a kapcsolat az alábbi két tulajdonság között: (a) egy CF nyelv determinisztikus, azaz létezik hozzá determinisztikus veremautomata (b) egy CF nyelvhez létezik determinisztikus CF nyelvtan 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. Készítsünk szigorúan jellemzõ nyelvtant az 1. feladatban leírt fordításhoz. Megoldás 5. Bizonyítsuk be: Ha egy fordításhoz van jellemzõ nyelvtan, akkor van hozzá szigorúan jellemzõ nyelvtan is. 6. 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. Gyakorolni való feladatok 7. Készítsünk olyan véges fordítót, mely minden $w \in \{a,b\}^*$ szó esetén annyi x -et ír ki, ahányszor a w szóban elõfordul az abaaba részszó! (Ha pl. w = aabaabaababab , akkor xx lesz az eredmény, mert kétszer, a második és az ötödik pozíciótól kezdve szerepel az abaaba a w szóban.) 8. 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 9. Készítsünk olyan fordító automatát, mely minden $w \in \{a,b\}^*$ szó esetén annyi 0-t ír ki, ahány olyan x kezdõszelete van w -nek, hogy x -ben az a -k és a b -k száma azonos.