Příklad 1.
Mějme konečný automat AI = {{qo,qi}>{a,b},5,qo,{qi}), kde přechodová funkce 6 je následující:
S(q0,a) = q1 S(q0,b) = q0
S(q1,a) = q0 S(q1,b) = qi
Pro lepší přehlednost uvádíme i stavový diagram automatu AI:
b b
Úkoly:
1. Zapište tabulku přechodové funkce 6.
2. Zapište výpočet automatu AI na slovech aa, ab, aha, abbaba, bbbaaa (výpočet zapi-sujte v konfiguracích).
3. Nalezněte všechna slova délky max. 3, které automat AI akceptuje.
4. Určete jazyk L(M).
1
Příklad 2.
Mějme konečný automat M = ({qo,Qi,Q2},{x,y},S,qo,{qo}), kde přechodová funkce ó je následující:
d(qo,x) = qi S{q0,y) = qi
= q2 5{qi,y) = <Z2
S(q2,x)=q0 S(q2,y) = qo
Pro lepší přehlednost uvádíme i stavový diagram automatu M:
Úkoly:
1. Zapište tabulku přechodové funkce 6.
2. Zapište výpočet automatu M na slovech xy, xyx, yyx, xyxy, xyyxx (výpočet zapi-sujte v konfiguracích).
3. Nalezněte všechna slova délky max. 3, které automat M akceptuje.
4. Určete jazyk L(M).
2
Příklad 3.
Mějme konečný automat M = ({qo, qi, q2, Q3}, {0,1}, 5, qo, {93}), kde přechodová funkce ó je následující:
%o, 1) = qi %i,0) = Q2 %i, 1) = 92
^(<?2,0) = g2 ô(q2,l)=q3 %3,0)=<?2 ó(q3,1) = (?3
Pro lepší přehlednost uvádíme i stavový diagram automatu M:
Úkoly:
1. Zapište tabulku přechodové funkce ó.
2. Zapište výpočet automatu M na slovech 11, 100, 101, 1101, 10010 (výpočet zapisujte v konfiguracích).
3. Nalezněte všechna slova délky max. 4, které automat M akceptuje.
4. Pokuste se definovat všechny podmínky pro to, aby nějaké slovo w G {0,1}* bylo akceptováno automatem M.
5. Určete jazyk L(M).
3
Příklad 4.
Mějme konečný automat M = ({qo, 91, 92> 93> 94}, {A, B}, 5, qo, {94}), kde přechodová funkce ó je následující:
%0	A)	= 9i			
%i	A)	= qi	%i	B)	= 92
5{q2	A)	= qi	S(q2	B)	= 93
%3	A)	= 94	£(93	B)	= 91
5{q4	A)	= 94	S(q4	B)	= 94
Pro lepší přehlednost uvádíme i stavový diagram automatu M: B A
A, B
Úkoly:
1. Zapište tabulku přechodové funkce 6.
2. Zapište výpočet automatu M na slovech AB, BBA, ABBA, BABBA, AABBAB (výpočet zapisujte v konfiguracích).
3. Nalezněte všechna slova délky max. 6, které automat M akceptuje.
4. Pokuste se definovat všechny podmínky pro to, aby nějaké slovo w G {A, B}* bylo akceptováno automatem M.
5. Určete jazyk L(M).
4