FORM LN JAZYKY A AUTOMATY I
Re en cvicen 7.
1. Po aplikaci algoritmu pro odstranen lev rekurze a n sledn substituci netermin lu obdrme
n sleduj c gramatiku:
S ! number j ( S B j number T0 j ( S B T0 j
number L0 j( S B L0 j number T0 L0 j( S B T0 L0 j
number S0 j( S B S0 j number T0 S0 j( S B T0 S0 j
number L0 S0 j ( S B L0 S0 j number T0 L0 S0 j ( S B T0 L0 S0
S0 ! and L S0 j or L S0 jand L j or L
L ! number j ( S B j number T0 j ( S B T0 j
number L0 j( S B L0 j number T0 L0 j( S B T0 L0
L0 ! + T L0 j T L0 j + T j T
T ! number j ( S B j number T0 j ( S B T0
T0 ! F T0 j = F T0 j F j = F
F ! number j ( S B
B ! )
2. Z sobn kov automat akceptuj c L(G) je A = (fqg; fa; b; cg; fS; A; B; C; a; b; cg; ; q; A; ;),
(q; "; A) = f(q; BBC); (q; CaaB); (q; c)g
(q; "; B) = f(q; AabB); (q; Ba); (q; ab)g
(q; "; C) = f(q; cc); (q; BA); (q; ")g
(q; a; a) = f(q; ")g
(q; b; b) = f(q; ")g
(q; c; c) = f(q; ")g
3.
L(A) = f w 2 fa1; a2; a3; b1; b2g+ j
3 ]a1 (w) + ]a2(w) + 5 ]a3(w) + 1 = ]b1 (w) + ]b2(w)
a pro ka d vlastn pre x u slova w plat
3 ]a1 (u) + ]a2(u) + 5 ]a3(u) ]b1(u) + ]b2(u)g
4. Ka d pravidlogramatikyH = (N; T; P; S),kter je vGreibachov norm ln m tvaru,je typu
X ! aY, kde X 2 N; a 2 T; Y 2 N . Pro libovoln retezy s; t takov , e s =)H t, je pocet
termin ln ch symbolu v slove t (oznacujeme ]T(t)) pr ve o jedno vet , ne v slove s. Kdy
tedyr0 = S =)H r1 =)G r2 : : : =)G rk = r jeodvozen slovad lkyl,tak]T(ri) = ]T(ri 1)+1
pro v echna i, 1 i k. Pokud nav c vezmeme do vahy, e ]T(r0) = 0 a ]T(r) = l, mus
b t d lka tohoto odvozen pr ve l.
1