Sziasztok!

Először megbeszéltük a zh-ból a 4. feladatot. A megoldás lényege az, hogy az üres veremmel való elfogadás esetén veszítenének a veremautomaták az erejükből, mert az $\epsilon$ szót sose bírnák elfogadni, míg az állapottal való elfogadás esetén nem veszítenének: a Greibach normálformára alapozva, meg arra a konstrukcióra, amivel egy CF nyelvtanból veremautomatát csináltunk (az első ilyen konstrukció, az, ami a ballevezetést csinálja), minden CF nyelvtanhoz tudunk készíteni egy olyan állapottal elfogadó automatát, ami nem tartalmaz $\epsilon$-szabályt.

Az óra igazi anyaga:
1. Véges fordítás (lásd az 1. és 2. feladatot), hogyan lehet a fordítandó nyelv véges automatájából és a véges fordítóból megszerkeszteni a fordított nyelv véges automatáját (ami épp ezért szintén reguláris lesz). Ezt néztük a 3. példán, számolós, de ha gondolkodunk, akkor rövidebben is megy. Beadandó a 4. feladat megoldása. Volt még említve, hogy a CF nyelvek is zártak a véges fordításra. Gyakorolni van a 7. és 8. feladat.

2. Veremfordító, egyszerű szintaxis vezérelt fordítási séma, ezek egyenértékűsége.
Gyakorolni van a 9. feladat.

3. Jellemző és szigorúan jellemző nyelvtanok (5. és 6. példa).

Fordításelmélet

Formális nyelvek gyakorlat (8)

2000. április 4., 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. Készítsünk szigorúan jellemző nyelvtant az 1. feladatban leírt fordításhoz.

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

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.

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.