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!



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 q₀.