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.