4. gyakorlat

1. feladat Adott az alább specifikált kétirányban mozgó véges automata: d(S,a)=(P,e) d(S,b)=(Q,e) d(P,a)=(R,e) d(P,b)=(Q,e) d(Q,a)=(S,h) d(Q,b)=(T,e) d(R,a)=(V,h) d(R,b)=(V,h) d(T,a)=(V,h) d(T,b)=(V,h) d(V,a)=(S,e) d(V,b)=(S,e) Valamennyi állapot elfogadó állapot. Készíts az automata által elfogadott nyelvre egyirányban mozgó véges automatát! 2. feladat Adott az alábbi kétirányban mozgó véges automata: d(P,a)=(Q,e) d(P,b)=(R,e) d(Q,a)=(U,e) d(Q,b)=(W,h) d(R,a)=(P,h) d(R,b)=(V,e) d(U,a)=(W,h) d(U,b)=(Q,h) d(V,a)=(W,h) d(V,b)=(W,h) d(W,a)=(P,e) d(W,b)=(P,e) q0=P, F={Q,V}. Készíts az automata által elfogadott nyelvre egyirányban mozgó véges automatát! 3. feladat Legyen Szigma={a,b}. A nyelv azon jelsorozatokból áll, ahol |a|=|b|. Bizonyítsd be, hogy ez a nyelv nem reguláris! 4. feladat Reguláris-e az {ambn | 1 <= m <= n} nyelv? 5. feladat Bizonyítsuk be, hogy az L={xx | x eleme {a,b}*} nyelv nem reguláris! 6. feladat Reguláris-e a {0i1j | (i,j) != 1} nyelv? 7. feladat Adjunk determinisztikus véges automatát a 10+(0+11)0*1 reguláris kifejezéshez! 8. feladat Adjunk determinisztikus véges automatát a 01(((10)*+111)*+0)*1 reguláris kifejezéshez! 9. feladat Adott két nyelv az alábbi két egyenletrendszerrel. Készítsd el a két nyelv metszetét felismerõ minimálautomatát! S1=aS1+b(A+epszilon) S2=aS2+b(B+epszilon) A=bS1+a(A+epszilon) B=aS2+b(B+epszilon) 10. feladat Az L nyelv alfabetája Szigma={a,b}. A nyelv mondatai azok a nem üres jelsorozatok, amelyekben van legalább egy páros hosszúságú teljes homogén részsorozat. Szerkessz minimálautomatát a következõ nyelvekre: L L2 L and L2 L* 11. feladat Szerkesszük meg az alábbi automata minimálautomatáját, majd írjuk fel az automata által elfogadott nyelvet reguláris kifejezés formájában! 12. feladat Egy nyelv karakterkészlete Szigma={a,b,c}. A nyelv mondataira a következõ megállapítások érvényesek: Minden mondatban mindhárom karakter elõfordul. Amennyiben két szomszédos karakter nem azonos, akkor a karakter után csak b, b után csak c, c karakter után csak a karakter következhet. Írd föl a nyelvet reguláris kifejezés formájában! 13. feladat Adjunk reguláris kifejezést az alábbi automata által elfogadott nyelvre! 14. feladat Mely szavakból áll az a nyelv, amelyet az alábbi reguláris kifejezés ír le? (a+b)*[aa(a+b)*bb+bb(a+b)*aa](a+b) * Adjunk meg ehhez a nyelvhez egy determinisztikus véges automatát! 15. feladat A Szigma={a,b} halmazon adott két nyelv az alábbi verbális specifikációval: L1: A mondatban van legalább egy páros hosszúságú homogén részsorozat. L2: A mondat hossza páros vagy nulla. Rajzold fel az L1, az L2 és az L1L2 nyelvet elfogadó minimálautomatákat!

Varró Gergely gervarro@cs.bme.hu

Utolsó módosítás dátuma: 2004. március 5.