Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
§1.1.Niektóreszczególnezbiory
21
WtymprzypadkuzbiórΣ∗zawieraa,b,ab,ba,bab,babbabb
itp.ZnówzbiórΣ∗jestnieskończony.
(c)JeśliΣ={0,1},tozbiórBtychsłówzezbioruΣ∗,które
zaczynająsięod1,jestdokładniezbioremrozwinięćdwójkowych
liczbcałkowitychdodatnich.Toznaczy
B={1,10,11,100,101,110,111,1000,1001,...}.
IstniejewΣ∗pewneszczególnesłowo,wpewnymsensieana-
logicznedozbiorupustego,nazywanesłowempustym;jestto
ciągniezawierającywcaleliterioznaczanyprzezλ(małagrecka
literalambda).
PRZYKŁAD4
(a)JeśliΣ={a,b},to
Σ∗={λ,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,...}.
(b)JeśliΣ={0,1,2},to
Σ∗={λ,0,1,2,00,01,02,10,11,12,20,21,22,000,001,002,...}.
(c)JeśliΣ={a},to
Σ∗={λ,a,aa,aaa,aaaa,aaaaa,aaaaaa,...}.
Wtymprzykładzienieznajdziemyżadnychinteresującychjęzy-
ków,alebędzieondobrzeilustrowałróżnewprowadzanepojęcia.
(d)Różnejęzykiprogramowaniaspełniająnasządefinicjęję-
zyka.Naprzykład,alfabetΣpewnejwersjijęzykaALGOLma
113elementów;zbiórΣskładasięzliter,cyfr0,1,2,...,9iwielu
operatorów,wtymrównieżoperatorówzbudowanychzciągówli-
ter,takichjak„goto”i„if”.Jakzwykle,Σ∗zawierawszystkie
możliweskończoneciągiliterzezbioruΣ,niezależnieodichzna-
czenia.PodzbiórzbioruΣ∗,składającysięztychciągów,które
zostajązaakceptowanewczasiedziałaniakompilatorajęzykaAL-
GOLnadanymkomputerze,jestdobrzezdefiniowanymiużytecz-
nympodzbioremzbioruΣ∗;możemygonazwaćjęzykiemAL-
GOLokreślonymprzeztenkompilator.
Omówimyterazniezbędneograniczenianakładanenazbiór
Σ.Problempojawiasięwtedy,gdyliteryalfabetuΣsamesą
zbudowanezinnychliterztegosamegozbioruΣlubzjakiegoś
innegoalfabetu.Naprzykład,jeślizbiórΣzawierajakolitery
symbolea,biab,tociągaabmożebyćrozumianyjakociąg
trzechlitera,aibzΣlubjakociągdwóchliteraiab.Nie
możnastwierdzić,którymztychciągówmaonbyć,imaszyna
