FORM LN JAZYKY A AUTOMATY I
CVI EN 2.
1. Popi te jazyk generovan gramatikou G = (fS;A;Bg;fa;bg;P;S), p i em mno ina pravidel
P obsahuje n sleduj c pravidla:
P : S ! aA S ! bB S ! a
A ! aS A ! aA A ! bB
B ! bB B ! a B ! b
2. Navrhn te regul rn gramatiky pro n sleduj c jazyky:
A = f w j w 2 fa;bg ; w neobsahuje podslovo abbabg.
B = (f0gf0;1g2f2g ) f1g(f0gf1g)2 f2g+.
C = fw 2 fa;bg j ]a(w) mod 30 = 1; ]b(w) mod 27 = 3; w obsahuje podslovo abbg
3. Popi te jazyky rozpozn van n sleduj c mi kone n mi automaty:
a) A = (fq0;q1g; fx;yg; ; q0; fq1g)
: (q0; x) = q1 (q0; y) = q1
(q1; x) = q0 (q1; y) = q1
b) A = (fq0;q1;p1;p2;p3;r1;r2;r3g; fa;bg; ; q0; fq0g)
: (q0; a) = p1 (q0; b) = r1
(p1; a) = p2 (p1; b) = q0
(p2; a) = p3 (p2; b) = p1
(p3; a) = q1 (p3; b) = p2
(r1; a) = q0 (r1; b) = r2
(r2; a) = r1 (r2; b) = r3
(r3; a) = r2 (r3; b) = q1
(q1; a) = q1 (q1; b) = q1
4. Navrhn te deterministick kone n automaty rozpozn vaj c jazyky:
a) L = fw 2 fa;bg j w neobsahuje podslovo abag
b) L = fw 2 f0;1g j w kon et zcem 101g
c) L = fabg fabg fabag