1. feladat
Adjunk véges fordítót, amely az alábbi dolgokat 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.
|
2. feladat
Készítsünk véges fordítót az alábbi specifikáció alapján: legyen
Szigma={a,b}. 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. feladat
A 2. feladatban szereplő 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. feladat
A fordító ugyanaz, mint a 2. feladatban. A fordítandó nyelv: a szavak
a-val kezdődnek, b-re végződnek, és a páros hosszú
b sorozatok száma páratlan. Készíts a fordított nyelvre
automatát!
|
5. feladat
Készítsünk szigorúan jellemző nyelvtant az 1. feladatban leírt
fordításhoz!
|
6. feladat
Bizonyítsuk be, hogy ha egy fordításhoz van jellemző nyelvtan, akkor
van hozzá szigorúan jellemző nyelvtan is!
|
7. feladat
Készítsünk olyan véges fordítót, mely minden w eleme
{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. feladat
Készítsünk olyan fordító automatát, mely minden w eleme
{a,b}* szó esetén annyi nullá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.
|
9. feladat
Adott az alábbi fordító automata:
| delta(q0,a)=(q1,epszilon) |
delta(q0,b)=(q2,epszilon) |
| delta(q1,a)=(q0,epszilon) |
delta(q1,b)=(q0,x) |
| delta(q2,a)=(q0,y) |
delta(q2,b)=(q0,epszilon) |
Készíts automatát az
S -> aaSbb | bSa | epszilon
nyelvtan által generált nyelv fordításának felismerésére!
|
10. feladat
Tekintsük az alábbi szintaxis vezérelt fordítási
sémákat (Szigma={a,+,*,(,)},
Delta={1,2,3,4,5,6}):
-
| E -> E+T - 1ET |
| E -> T - 2T |
| T -> T*F - 3TF |
| T -> F - 4F |
| F -> (E) - 5E |
| F -> a - 6 |
-
| E -> E+T - ET1 |
| E -> T - T2 |
| T -> T*F - TF3 |
| T -> F - F4 |
| F -> (E) - E5 |
| F -> a - 6 |
Mi a fordított nyelv?
|
11. feladat
Készíts olyan szintaxis vezérelt fordítási sémát, amely a száznál
kisebb arab számokat római számokká írja át. Add meg a fordítás egy
jellemző nyelvtanát is!
|
|