Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
22
1.Zbiory,ciągiifunkcje
czytającaliterya,a,bpojednejniebyłabywstaniezinterpreto-
waćtychdanychwejściowychjednoznacznie.Weźmyinnyprzy-
kład.JeśliΣzawieraab,abaibab,tociągwejściowyabababmoże
byćzinterpretowanyalbojako(ab)(ab)(ab),albojako(aba)(bab).
Abyuniknąćtakichproblemów,niepozwolimynato,byzbiórΣ
zawierałjakiekolwieklitery,któresamesąciągamiliterrozpoczy-
nającymisięodliterynależącejdoΣ.Zatemdopuścimyzbiory
Σ={a,b,c},Σ={a,b,ca},Σ={a,b,Ab},aleniedopuścimy
aniΣ={a,b,c,ac},aninawetΣ={a,b,ac}.
Poprzyjęciutejumowymożemyjednoznacznieokreślićdłu-
gośćsłowawzΣ∗(długość(w))jakoliczbęliteralfabetuΣ
wsłowiew,zliczająckażdewystąpienielitery.Naprzykład,
jeśliΣ={a,b},todługość(aab)=długość(bab)=3.Je-
śliΣ={a,b,Ab},todługość(abbAb)=4.Określmytakże
długość(λ)=0.Bardziejprecyzyjnadefinicjadługościjestpo-
danaw§7.1.
Jeszczejednauwaganazakończenie:będziemyużywaćsym-
boliw,w1itd.jakonazwzmiennychdlasłów.Niepowinnopro-
wadzićtodonieporozumień,pomimożeliterawjestteżliterą
alfabetupolskiego.
PRZYKŁAD5
JeśliΣ={a,b}orazA={w∈Σ∗:długość(w)=2},to
A={aa,ab,ba,bb}.Jeśli
B={w∈Σ∗:długość(w)jestliczbąparzystą},
toBjestzbioremnieskończonym{λ,aa,ab,ba,bb,aaaa,aaab,
aaba,aabb,...}.Zauważmy,żeAjestpodzbioremB.
ĆWICZENIADO§1.1
1.Wypiszpopięćelementówkażdegoznastępującychzbiorów:
(a){n∈N:liczbanjestpodzielnaprzez5},
(b){2n+1:n∈P},
(c)P({1,2,3,4,5}),
(d){2
(e){1/n:n∈P},
(f){r∈Q:0<r<1},
n:n∈N},
(g){n∈N:liczban+1jestpierwsza}.
2.Wypiszelementynastępującychzbiorów:
(a){1/n:n=1,2,3,4},
(b){n
2-n:n=0,1,2,3,4},
(c){1/n
2:n∈P,liczbanjestparzystain<11},
(d){2+(-1)
n:n∈N}.
