FORM LN JAZYKY A AUTOMATY I
Re en sady probl mu 4.
1. Necht' A = (K; fa; bg; ; q0; F) je konecn automat akceptuj c jazyk L.
Zkonstruujemenejdr venedeterministick konecn automatA0 akceptuj c jazykfagfa; bg fag.
A0 = (K0; fa; bg; 0; 1; F0), pricem :
K0 = f1; 2; 3g;
F0 = f3g;
0 : 0(1; a) = f2g
0(1; b) = ;
0(2; a) = f2; 3g
0(2; b) = f2g
0(3; a) = 0(3; b) = ;
Automat A akceptuj c jazyk L = L \ fagfa; bg fag je kart zsk m soucinem automatu A a
A0.
A = (K; fa; bg; ; q0; F), pricem :
K = K K0;
q0 = (q0; 1);
F = F F0;
: ((p; s); x) = f(r; t) j r 2 (p; x); t 2 0(s; x)g
pro v echna p 2 K; s 2 K0; x 2 fa; bg.
2. Necht' G = (N; ; P; S) je regul rn gramatika, t.j. v echna jej pravidla jsou tvaru
A ! xB anebo A ! x (A; B 2 N; x 2 ). Proto odvozen slova w = x2x1 v gramatice G
je tvaru S =) x2X =) x2x1. Vytvor me gramatiku G0, kter nejprve vygeneruje c st x1, a
pak c st x2.
G0 = (N0; ; P0; S0), pricem mno ina netermin lu N0 obsahuje symboly
N0 = fAi;Y j A; Y 2 N; i = 1; 2g fS0g,
(S0 jenov poc tecn netermin l;netermin lAi;Y znac , eodvozov n zacalonetermin lem
Y a odvozuje se slovo xi).
Mno ina pravidel P0 = P0 P1 P2, kde
P0 = fS0 ! Y1;Y j Y 2 Ng
(zac name simulovat odvozen slova x1 od netermin lu Y)
P1 = fA1;Y ! aB1;Y j A ! aB 2 Pg fA1;Y ! aS2;Y j A ! a 2 Pg
(simulace odovozen X =) x1, resp. prechod na simulaci S =) x2X.)
P2 = fA2;Y ! aB2;Y j A ! aB 2 Pg fA2;Y ! a j A ! aY 2 Pg
(simulace odovozen S =) x2X, resp. jej ukoncen , kdy je skutecne mo n odvodit v G
vetu x2Y a Y je netermin l, z kter ho bylo generov no x1.
1
3. Nejmen tr da jazyku, obsahuj c v echny konecn jazyky a uzavren vzhledem k operac
m sjednocen , prunik a komplement ( v dal m ji budeme oznacovat T) je vlastn podmno
inou mno iny regul rn ch jazyku R.
Inkluze T R je dusledkem uz verov ch vlastnost tr dy R (konkr tne: ka d konecn
jazyk je regul rn a tr da regul rn ch jazyku je uzavrena vzhledem k operac m sjednocen ,
pruniku a komplementu). Existence regul rn ho jazyka nepatr c ho do tr dy T je dusledkem
n sleduj c ho tvrzen :
T: Necht' L 2 T, L . Pak bud' jazyk L je konecn , anebo komplement jazyka L, Lc = L, je
konecn .
Nyn stac uv itjazykfaag .Jdeonekonecn regul rn jazyk,kter hokomplementfagfaag
je taky nekonecn , a podle predch zej c ho tvrzen T nepatr do tr dy T.
Dok emeplatnosttvrzen T.Pridukazuvyjdemezfaktu, eka d jazykL tr dyT vznikne
konecn m poctem operac ; \; c zkonecn ch jazyku. De nujeme hloubku jazykaL,hl(L),
jako pocet operac potrebn ch k vytvoren jazyka L takto:
hl(L) =
8
>><
>>:
0 kdy L je konecn
hl(L1) + hl(L2) + 1 kdy L je nekonecn a L = L1 L2; L1; L2 2 T
hl(L1) + hl(L2) + 1 kdy L je nekonecn a L = L1 \L2; L1; L2 2 T
hl(L1) + 1 kdy L je nekonecn a L = Lc
1; L1 2 T
Tvrzen dok eme indukc vzhledem k hloubce jazyka L.
1 Necht' L 2 T a hl(L) = 0. Pak jazyk L je konecn a tvrzen plat .
2 Predpokl dejme, e tvrzen plat pro v echny jazyky hloubky men ne n; n > 0. Dok
eme jej pro jazyky hloubky n. Predpokl dejme proto, e L 2 T a hl(L) = n. Pak L je
nekonecn a plat jedna z n sleduj c ch mo nost :
L = L1 L2, pricem hl(L1) < n, hl(L2) < n a nutne alespon jeden z jazyku L1; L2
je nekonecn . Podle indukcn ho predpokladu je bud' Lc
1 nebo Lc
2 konecn . Ale
Lc = (L1 L2)c = Lc
1 \Lc
2, a proto komplement jazyka L je konecn .
L = L1 \ L2, pricem hl(L1) < n, hl(L2) < n a nutne oba jazyky L1; L2 jsou nekonecn
. Pak ale podle indukcn ho predpokladu jejich komplementy jsou konecn .
Ale Lc = (L1 \L2)c = Lc
1 Lc
2, a proto jazyk L je konecn .
L = Lc
1, pricem hl(L1) < n a Lc
1 je nekonecn . Pak ale podle indukcn ho predpokladu
je L1 konecn , a tedy i komplement jazyka L je konecn .
2