FORM LN JAZYKY A AUTOMATY I
Re en cvicen 6.
1. Jazykfanbn jn 1g+ jegenerov ngramatikouG = (fS;X;Xa;Xb;A;Bg;fa;bg;P;S),pricem
mno ina pravidel P je tvaru
P : S ! XS j XX j AXb j AB
X ! AXb j AB
Xb ! XB
A ! a
B ! b
2. Necht' G = (N;T;P;S) je gramatika v Chomsk ho norm ln m tvaru. Gramatika G obsahuje
dva typy pravidel: pravidla patr c do N (N N) (nazveme je netermin ln ) a pravidla z
N T(nazvemejetermin ln ).Necht'S =)G w1 =)G w2 ::: =)G wn = wjeodvozen d lky
n; w 2 L(G). Proto e se jedn o bezkontextovou gramatiku, ve kter dn pravidlo nem
na prav strane termin ln symbol, mu eme predpokl dat, e v uveden m odvozen byla
nejdr ve aplikov na netermin lov pravidla a a potom termin lov pravidla. Bud' tedy i
maxim ln c slo takov , e wi 2 N+. Proto e se ka d netermin l prep e na pr ve jeden
termin l, je jwij = jwj. Na odvozen termin ln ho retezu ze slova wi je potrebn ch pr ve
jwj kroku. Slovo wi bylo odvozeno z poc tecn ho netermin lu aplikac netermin lov ch
pravidel, z nich ka d zvet d lku retezu pr ve o 1. Proto na odvozen retezu wi bylo
zapotreb jwj 1 kroku. Secten m: n = jwj+ jwj 1 a tedy n+1
2 = jwj:
3. Konstrukce gramatiky G spoc v v n sleduj cich trech kroc ch.
(i) Mno inu netermin lu N roz rime o nov netermin ly, jeden pro ka d termin ln
symbol z T, t.j. N = N fNa j a 2 Tg.
(ii) Mno inu pravidel P transformujeme tak, e ka d v skyt termin lu a nahrad me pr slu
n m netermin lem Na. t.j.
P = f 1 ::: k ! 1 ::: l j x1 :::xk ! y1 :::yl 2 P;
i = xi pro xi 2 N;
i = Nxi
pro xi 2 T;
i = yi pro yi 2 N;
i = Nyi
pro yi 2 Tg
(iii) Nakonec do mno iny pravidel P prid me pravidla, umo nuj c prepis nov ch netermin
lu na termin ly, t.j.
P = P fNa ! a j pro v echny netermin ly Na 2 N Ng.
V echny nove pridan pravidla jsou regul rn . Transformac v bode (ii) se mu e poru it
regularita pravidel. Proto navr en algorimus zkonstuuje k regul rn gramatice G gramatiku
G , kter nemus b t nutne regul rn , ale jiste je bezkontextov . Pro ostatn gramatiky
konstrukce zachov va typ gramatiky.
4. a)L1 \L2 = fa1ba2ba3b:::ajb j j 2; j sud g.
b) Predpokl dejme, e jazyk L1 \ L2 je bezkontextov . Pak podle pumping lemy pro bezkontextov
jazyky existuje c slo p takov , e pro v echna slova w 2 L1 \ L2, jwj > p jsou
splneny n sleduj c podm nky:
(a) 9u;v;x;y;z : w = uvxyz,
(b) jvyj > 0; jvxyj < p,
(c) 8i 0 : uvixyiz 2 L1 \L2.
Zvolme napr klad slovo w = a1ba2b:::apb. Skusme naj t slova u;v;x;y;z splnuj c 1. 3.
Zrejme v 6= b, y 6= b (slovo z L1 \ L2 nemu e obsahovat podretezec bb). Kdyby v = ai
(anebo v = ai), tak napumpov van m podle 3. se zmen pocet symbolu a v pr slu n skupine
a poru se vztah mezi poctem symbolu a ve sousedn ch skupin ch. Kdyby v = aibaj
(anebo v = aibaj), tak napumpov van m podle 3. dost vame slovo, ve kter m dve po sobe
jdouc skupiny symvolu a maj stejnou d lku.
1