Formális nyelvek gyakorlat (10)

2001., április 17., kedd

1. Véges fordító kell, melynek bemenõ ábécéje 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. Adj olyan fordítót, ami minden $\{a,b\}$ feletti szót lefordít, majd adj egy olyant is, ami csak a $b$-re végzõdõ szavakat fordítja le!

2. 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.)

3. Készítsünk olyan veremfordító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.

4. Az egyes feladat elsõ fordítójá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?

5. (a) Adj egyszerû szintaxis vezérelt fordítási sémát, ami a prefix alakú aritmetikai kifejezéseket fordítja át infix alakba!
(b) A séma segítségével készítsd el a $+a*a+aa$ szó fordítását!

6. Gondolkodni!!!
A fordító legyen újra az egyes példa elsõ fordítója. A fordítandó nyelv a
$\{ww^{-1}\;\vert\;w\in{\{a,b\}}^*\}$. Nyelvtan kell a fordítottra.

7. HÁZI FELADAT, BEADHATÓ
A fordító megint legyen az egyes példa elsõ fordítója. 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.