3. gyakorlat

1. feladat (Szigma={0,1}) A nyelv azon jelsorozatok összessége, amelyekben nincs három darab 0 egymás mellett. Reguláris ez a nyelv? 2. feladat Szerkesszük meg az alábbi automata minimálautomatáját! 3. feladat Szigma={0,1} A belõlük alkotható jelsorozatokat, mint egész számokat fölfogva, a nyelv legyen a hárommal osztható (3=011) számok összessége. Minimálautomata kéretik. 4. 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. Készíts minimálautomatát a fent definiált nyelvre! 5. feladat Homogén részsorozat az a nem üres karaktersorozat, amelynek karakterei azonosak. Egy homogén részsorozat teljes, ha az nem terjeszthetõ ki, vagyis határoló karakterei - ha vannak - különböznek a sorozatot alkotó karakterektõl. Egy teljes homogén részsorozat páratlan ill. páros, ha a sorozatot alkotó karakterek száma páratlan ill. páros. Legyen (Szigma={a,b}). Az L nyelv mondatai legyenek azok a nem üres jelsorozatok, melyekben minden teljes homogén részsorozat hossza páratlan. Készíts minimálautomatát, amely az L nyelvet fogadja el! Az L2 nyelvet definiáljuk úgy, hogy azon karaktersorozatokat tartalmazza, amelyek felírhatók két L-beli mondat konkatenációjaként. Készítsünk minimálautomatát az L2 nyelvre! 6. feladat Minimalizáljuk az alábbi ábrán látható automatát! 7. feladat Adjunk minimálautomatát azon Szigma={a,b,c} feletti nyelvhez, melybe azok a nemüres szavak tartoznak, amelyekben a szó utolsó betûje máshol nem szerepel a szóban. 8. feladat Legyen egy két irányban mozgó automata szabályrendszere a következõ: d(S,a)=(P,e) d(S,b)=(Q,e) d(P,a)=(P,e) d(P,b)=(Q,e) d(Q,a)=(S,h) d(Q,b)=(S,e) d(R,a)=(P,e) d(R,b)=(P,h) q0=S, F={S,P} Készíts minimálautomatát az automata által elfogadott nyelvre! 9. feladat Egy kétirányú mozgást végzõ véges automata mozgási szabályai a következõk: d(S,a)=(S,e) d(S,b)=(A,h) d(A,a)=(B,e) d(A,b)=(C,h) d(B,a)=(C,h) d(B,b)=(A,e) d(C,a)=(C,h) d(C,b)=(C,h) Az induló állapot természetesen S, míg F={S,A,B}. Szerkessz vele egyenértékû egyirányú automatát! 10. feladat Egy nyelv ábécéje Szigma={a,b,c}. Kétirányú mozgást végzõ automatájának mozgási szabályai a következõk: d(S,a)=(A,e) d(S,b)=(B,e) d(S,c)=(C,e) d(A,a)=(D,h) d(A,b)=(B,e) d(A,c)=(S,h) d(B,a)=(S,h) d(B,b)=(D,h) d(B,c)=(C,e) d(C,a)=(A,e) d(C,b)=(S,h) d(C,c)=(D,h) d(D,a)=(S,e) d(D,b)=(S,e) d(D,c)=(S,e) q0=S, F={S,A,B,C,D} Szerkesszünk az elõzõ automatával ekvivalens egyirányú automatát!

Varró Gergely gervarro@cs.bme.hu

Utolsó módosítás dátuma: 2004. február 23.