Sziasztok!

A mai órán nagyon sok minden volt (érzésem szerint túl sok is, de most már mindegy).

Először is kis zh volt, eredmények itt.

Másodszor: valószínűleg nem lesz jegyzet a tárgyhoz, próbáljatok meg felsőbbévesektől (kölcsön)kérni, fénymásolni.

Volt minimalizálás: ehhez megcsináltuk az 1. feladatot, otthonra maradt a 2. és 3.. Ezekről nem fogunk beszélni, csak konzultáción, meg ha valakit érdekel, akkor óra után.

Az óra anyaga főleg a kétirányú véges automaták voltak. Ehhez segédvackok kérdések és válaszok formátumban. Értelemszerűen előbb a kérdéseket kell megnézni, aztán a válaszokat. : )

Feltettem még egy anyagot a 2VA-król , itt egy kicsit máshogy van leírva a 2VA, mint a kérdés-válasznál. Lehet próbálkozni, kinek melyik megközelítés jön be jobban.

Amúgy megbeszéltük a 2VA-kat, de ez olyan dolog, amit nektek magatoknak kell megemészteni. Tegyétek ezt. Következő óra elején megoldjuk a 4. és 5. feladatot, a 6. és a 7. meg majd a jövő órán lesz házi.

Formális nyelvek gyakorlat (3)

2000. szeptember 25., hétfő

1. Adjuk meg az alábbi automatához tartozó minimálautomatát!

\includegraphics{r9.eps}

2. Készítsünk minimálautomatát az alábbi nyelvhez:
$L =\{ w : \vert w\vert _a \mbox{ páros},
\vert w\vert _b \mbox{ páros és }
\vert w\vert \mbox{ osztható 4-gyel}\}$

3. Legyen $\Sigma=\{a,b\}$ és álljon az L nyelv azokból a szavakból, melyekben minden három hosszú részszó (ha egyáltalán van ilyen) legalább 2 darab a betűt tartalmaz Készíts minimálautomatát az L nyelvhez!

4. Legyen egy kétirányú mozgást végző automata szabályrendszere a következő:




$\delta(S,a)=(P,e)$


$\delta(S,b)=(Q,e)$


$\delta(P,a)=(P,e)$


$\delta(P,b)=(Q,e)$


$\delta(Q,a)=(S,h)$


$\delta(Q,b)=(S,e)$
Kezdőállapot az S, elfogadó állapotok az S és a P. Készítsen minimálautomatát a fenti automata által elfogadott nyelvre!

5. Adott az alábbi kétirányban mozgó véges automata:



$\delta(S,a)=(P,e)$


$\delta(S,b)=(Q,e)$


$\delta(R,a)=(V,h)$


$\delta(R,b)=(V,h)$


$\delta(P,a)=(R,e)$


$\delta(P,b)=(Q,e)$


$\delta(T,a)=(V,h)$


$\delta(T,b)=(V,h)$


$\delta(Q,a)=(S,h)$


$\delta(Q,b)=(T,e)$


$\delta(V,a)=(S,e)$


$\delta(V,b)=(S,e)$
Valamennyi állapot elfogadó állapot. Készítsen az automata által elfogadott nyelvre egyirányban mozgó véges automatát!

6. HF 1, írásban Legyen egy kétirányú mozgást végző automata szabályrendszere a következő:



$\delta(S,a)=(A,e)$


$\delta(S,b)=(B,e)$


$\delta(S,c)=(C,e)$


$\delta(A,a)=(D,h)$


$\delta(A,b)=(B,e)$


$\delta(A,c)=(S,h)$


$\delta(B,a)=(S,h)$


$\delta(B,b)=(D,h)$


$\delta(B,c)=(C,e)$


$\delta(C,a)=(A,e)$


$\delta(C,b)=(S,h)$


$\delta(C,c)=(D,h)$


$\delta(D,a)=(S,e)$


$\delta(D,b)=(S,e)$


$\delta(D,c)=(S,e)$
Az automata minden állapota elfogadó állapot. Szerkessze meg az egyenértékű egyirányú minimálautomatát!

7. HF 2, írásban Milyen nyelvet fogad el az alábbi kétirányú véges automata?
$\delta(q_0,a)$ = (q0,e) $\delta(q_0,b)$ = (q1,h)
$\delta(q_1,a)$ = (q2,e) $\delta(q_1,b)$ = (q3,h)
$\delta(q_2,a)$ = (q3,h) $\delta(q_2,b)$ = (q0,e)
$\delta(q_3,a)$ = (q3,h) $\delta(q_3,b)$ = (q3,h)
Elfogadó állapot a q0.