FORM LN JAZYKY A AUTOMATY I
e en sady probl m 2.
1. L(G) = (a b+
fa;bg a+
) faag
2. GA = (fS0;S;Sa;Sab;Sabb;Sabba;Sabbabg;fa;bg;P;S0), kde mno ina pravidel P obsahuje
n sleduj c pravidla:
S0 ! a j b j bS j aSa j
S ! a j b j bS j aSa
Sa ! a j b j bSab j aSa
Sab ! a j b j bSabb j aSa
Sabb ! a j b j aSabba j bS
Sabba ! a j aSa
GB = (fS0;S;S0;S0f0;1g;S0f0;1gf0;1g;S1;S10;S101;S1010;S2g;f0;1;2g;P;S0), kde mnoina
pravidel P obsahuje n sleduj c pravidla:
S0 ! 0S0 j 1S1 j 2S2 j 2 j
S ! 0S0 j 1S1 j 2S2 j 2
S0 ! 0S0f0;1g j 1S0f0;1g
S0f0;1g ! 0 j 1 j 0S0f0;1gf0;1g j 1S0f0;1gf0;1g
S0f0;1gf0;1g ! 0S0 j 2S0f0;1gf0;1g j 2
S1 ! 0S10
S10 ! 1S101
S101 ! 0S1010
S1010 ! 1
S2 ! 2S2 j 2
GC = (N;fa;bg;P;Snic;0;0) , kde
N = fSk;i;j j 0 i 29;0 j 26; k 2 fnic;a;ab;abbgg
a mno ina pravidel P obsahuje n sleduj c pravidla:
Snic;0;j ! aSa;1;j j bSnic;0;(j+1) mod4 pro v echny p pustn hodnoty j
Sa;i;j ! aSa;(i+1) mod3;j j bSab;i;(j+1) mod4 pro v echny p pustn hodnoty i;j
Sab;i;j ! aSa;(i+1) mod3;j j bSabb;i;(j+1) mod4 pro v echny p pustn hodnoty i;j
Sabb;i;j ! aSabb;(i+1) mod3;j j bSabb;i;(j+1) mod4 pro v echny p pustn hodnoty i;j
Sabb;0;3 ! a
Sabb;1;2 ! b
Sab;1;2 ! b
3. a) fx;ygfy;xx;xyg
b) L(A) = fw 2 fa;bg j ]a(w) = ]b(w)
a pro ka d pre x u slova w plat j]a(u) ]b(u)j 3 g
4. a)
b a
a b a
b
b)
1 0 1
0
110
0
c)
a b a b a a b a
ab