FORM LN JAZYKY A AUTOMATY I
Re en cvicen 8.
1. a) A = (fqg; fa; e; +; ; (; )g; fR; K; I; D; a; e; +; ; (; )g; ; q; R; ;),
(q; "; R) = f(q; R+ K); (q; K)g
(q; "; K) = f(q; KI); (q; I)g
(q; "; I) = f(q; I ); (q; D)g
(q; "; D) = f(q; (R)); (q; a); (q; e)g
(q; x; x) = f(q; ")g pro v echna x 2 fa; e; +; ; (; )g
b) A = (fq; rg; fa; e; +; ; (; )g; fR; K; I; D; a; e; +; ; (; ); $g; ; q; $; frg),
(q; x; ") = f(q; x)gpro v echna x 2 fa; e; +; ; (; )g
(q; "; R + K) = f(q; R)g
(q; "; K) = f(q; R)g
(q; "; K + I) = f(q; K)g
(q; "; I) = f(q; K)g
(q; "; I ) = f(q; I)g
(q; "; D) = f(q; I)g
(q; "; (R)) = f(q; D)g
(q; "; a) = f(q; D)g
(q; "; e) = f(q; D)g
(q; "; $R) = f(r; ")g
2. a) A1 = (fp1; p2; q0; q1; fg; fa; bg; fa; Zg; ; p1; Z; ffg)
(p1; a; Z) = f(p2; Z)g
(p2; b; Z) = f(q0; Z0)g
(q0; a; Z) = f(q0; aZ)g
(q0; a; a) = f(q0; aa)g
(q0; b; a) = f(f; aa)g
(f; a; a) = f(q1; ")g
(q1; a; a) = f(q1; ")g
(q1; b; Z) = f(q0; Z)g
b) Ka d slovo w patr c do jazyka (L1 \ L2) splnuje alespon jednu z n sleduj c ch
podm nek:
s1: zac na symbolem b
s2: zac na retezem aa
s3: konc symbolem a
s4: neobsahuje symbol b
s5: obsahuje lich pocet symolu b
s6: w = ai1 bai2 : : : aik
b a existuje x takov , e ix + 1 6= ix+1
A = (fs; s1; s2; s2; s3; s4; s5; s5; s6; f; k; n; u; vg; fa; bg; fa; Zg; ; s; Z; ff; k; s4; s5g)
(s; "; Z) = f(s1; Z); (s2; Z); (s3; Z); (s4; Z); (s5; Z); (s6; Z)g
(s1; b; Z) = f(f; Z)g (f; a; Z) = (f; b; Z) = f(f; Z)g
(s2; a; Z) = f(s2; Z)g (s2; a; Z) = f(f; Z)g
(s3; b; Z) = f(s3; Z)g (s3; a; Z) = f(s3; Z); (k; Z)g
(s4; a; Z) = f(s4; Z)g
(s5; a; Z) = f(s5; Z)g (s5; b; Z) = f(s5; Z)g
(s5; a; Z) = f(s5; Z)g (s5; b; Z) = f(s5; Z)g
(s6; a; Z) = f(n; Z); (u; aZ)g
(n; a; Z) = f(n; Z)g (n; b; Z) = fs6; Z)g
(u; a; a) = f(u; aa)g (u; b; a) = fv; aa)g
(v; a; a) = f(v; ")g (v; b; a) = ff; Z)g
(v; a; Z) = f(f; Z)g
1
3. Hledan gramatika je tvaru
G = (fS; q0Z0q0]; q0Z0q1]; q0Xq0]; q0Xq1]; q1Z0q0]; q1Z0q1]; q1Xq1]g; f0; 1g; P; S),
pricem mno ina pravidel P obsahuje n sleduj c pravidla:
P : S ! q0Z0q0] j q0Z0q1]
q0Z0q0] ! 1 q0Xq0] q0Z0q0] j 1 q0Xq1] q1Z0q0] j
q0Z0q1] ! 1 q0Xq0] q0Z0q1] j 1 q0Xq1] q1Z0q1]
q0Xq0] ! 1 q0Xq0] q0Xq0] j 1 q0Xq1] q1Xq0] j 0 q1Xq0]
q0Xq1] ! 1 q0Xq0] q0Xq1] j 1 q0Xq1] q1Xq1] j 0 q1Xq1]
q1Z0q0] ! 0 q0Z0q0]
q1Z0q1] ! 0 q0Z0q1]
q1Xq1] ! 1
Gramatiku G lze d le zjednodu it na:
G0 = (fS; q0Z0q0]; q0Z0q1]; q0Xq1]; q1Z0q0]; q1Z0q1]; q1Xq1]g; f0; 1g; P; S),
pricem mno ina pravidel P obsahuje n sleduj c pravidla:
P : S ! q0Z0q0] j q0Z0q1]
q0Z0q0] ! 1 q0Xq1] q1Z0q0] j
q0Z0q1] ! 1 q0Xq1] q1Z0q1]
q0Xq1] ! 1 q0Xq1] q1Xq1] j 0 q1Xq1]
q1Z0q0] ! 0 q0Z0q0]
q1Z0q1] ! 0 q0Z0q1]
q1Xq1] ! 1
respektive na:
G00 = (fS; q0Z0q0]; q0Z0q1]; q0Xq1]g; f0; 1g; P; S),
pricem mno ina pravidel P obsahuje n sleduj c pravidla:
P : S ! q0Z0q0] j q0Z0q1]
q0Z0q0] ! 1 q0Xq1]0 q0Z0q0] j
q0Z0q1] ! 1 q0Xq1]0 q0Z0q1]
q0Xq1] ! 1 q0Xq1]1 j 01
pr padne a na:
G000 = (fS; q0Xq1]g; f0; 1g; P; S),
pricem mno ina pravidel P obsahuje n sleduj c pravidla:
P : S ! 1 q0Xq1]0S j
q0Xq1] ! 1 q0Xq1]1 j 01
jin mi slovy na:
G0000 = (fS; Xg; f0; 1g; P; S),
pricem mno ina pravidel P obsahuje n sleduj c pravidla:
P : S ! 1X0S j
X ! 1X1 j 01
2