FORM LN JAZYKY A AUTOMATY I
CVI EN 3.
1. Jsou d ny kone n automaty A1 a A2. Pou it m algoritm z p edn ky rozhodn te, jestli
jsou ekvivalentn , t.j. jestli L(A1) = L(A2).
A1 = (fq0;q1;q2;q3;q4;q5;q6;q7;q8;q9;q10g; fa;bg; ; q1; fq1;q8;q9g)
: (q0; a) = q3 (q0; b) = q8
(q1; a) = q2 (q1; b) = q7
(q2; a) = q3 (q2; b) = q8
(q3; a) = q10 (q3; b) = q0
(q4; a) = q5 (q4; b) = q10
(q5; a) = q1 (q5; b) = q6
(q6; a) = q7 (q6; b) = q10
(q7; a) = q8 (q7; b) = q4
(q8; a) = q0 (q8; b) = q5
(q9; a) = q2 (q9; b) = q10
(q10; a) = q10 (q10; b) = q10
A2 = (fB;C;D;E;F;Gg; fa;bg; ; C; fCg)
: (B; a) = B (B; b) = B
(C; a) = D (C; b) = F
(D; a) = G (D; b) = C
(E; a) = F (E; b) = B
(F; a) = C (F; b) = E
(G; a) = B (G; b) = D
2. a) Jazyk akceptovan kone n m automatem s k stavy je nekone n tehdy a jenom tehdy,
kdy obsahuje slovo w d lky k jwj < 2k. Doka te.
b) Nech jazyk akceptovan kone n m automatem s k stavy obsahuje nepr zdn slovo.
Pak obsahuje i nepr zdn slovo d lky men ne k . Doka te.
3. K dan mu nedeterministick mu kone n mu automatu skonstruujte (pou it m algoritmu z
p edn ky) ekvivalentn deterministick kone n automat. V sledn automat zapi te formou
tabulky.
A = (fq0;q1;q2;q3;q4g;fa;bg; ;q0;fq4g), kde
: (q0; a) = fq0g (q0; b) = fq0;q1g
(q1; a) = fq2g (q1; b) = fq2g
(q2; a) = fq3g (q2; b) = fq3g
(q3; a) = fq4g (q3; b) = fq4g
(q4; a) = ; (q4; b) = ;
4. Doka te, e gramatika G = (fS;A;Bg;fa;bg;P;S) s mno inou pravidel
P : S ! ABBS S ! ABB
AB ! BA BA ! AB
A ! a B ! b
generuje pr v jazyk L = fw 2 fa;bg j 2 ]a(w) = ]b(w) > 0g.