Poznámky k cvičeniu č. 1
Peter Kostolányi
25. septembra 2014
Označenia
Označenia nie sú v matematike úplne ustálené, čo môže v určitých situáciách viesť k nedorozumeniam. V nasledujúcom preto uvádzame krátky zoznam notačných dohôd, ktoré budeme v rámci
cvičení štandardne používať.
• Symbolom N označujeme množinu všetkých prirodzených čísel s nulou, t.j. N = {0, 1, 2, . . .}.
• Symboly ⊆, ⊇ označujú neostrú inklúziu.
• Symboly (, ) označujú ostrú inklúziu.
• Symboly 6⊆, 6⊇ označujú komplement neostrej inklúzie. Pre množiny S, T teda platí S 6⊆ T
práve vtedy, keď neplatí S ⊆ T .
• Symboly ⊂, ⊃ zvyčajne označujú neostrú inklúziu, ale možno sa stretnúť aj s ich použitím
na označenie ostrej inklúzie. Tieto symboly preto nebudeme používať.
Zobrazenia, obrazy a inverzné obrazy
Nech f : X → Y je zobrazenie. Obraz prvku x ∈ X pri zobrazení f sa tradične označuje symbolom
f (x). Pojem obrazu možno prirodzeným spôsobom rozšíriť aj na podmnožiny X.
Definícia 1. Nech f : X → Y je zobrazenie a X 0 ⊆ X. Obraz množiny X 0 pri zobrazení f je
množina
f (X 0 ) = {f (x) | x ∈ X 0 }.
Podobne možno definovať aj inverzný obraz množiny Y 0 ⊆ Y ako množinu všetkých prvkov
z X, ktoré sa zobrazia na prvok z Y 0 . Formálne:
Definícia 2. Nech f : X → Y je zobrazenie a Y 0 ⊆ Y . Inverzný obraz množiny Y 0 pri zobrazení
f je množina
f −1 (Y 0 ) = {x ∈ X | f (x) ∈ Y 0 }.
V prípade, že je zobrazenie f : X → Y bijektívne, zvykne sa symbolom f −1 označovať inverzné
zobrazenie k zobrazeniu f . Táto notácia súhlasí s notáciou inverzného obrazu zavedenou v definícii 2: inverzný obraz množiny Y 0 pri bijektívnom zobrazení f je obraz množiny Y 0 pri inverznom
zobrazení f −1 .
Inverzný obraz prvku y možno definovať pre ľubovoľné (teda nie len bijektívne) zobrazenia
ako inverzný obraz jednoprvkovej množiny {y}.
Definícia 3. Nech f : X → Y je zobrazenie a y ∈ Y . Inverzný obraz prvku y pri zobrazení f je
množina
f −1 (y) = f −1 ({y}) = {x ∈ X | f (x) ∈ {y}} = {x ∈ X | f (x) = y}.
V prípade, že je zobrazenie f bijektívne, je inverzný obraz f −1 (y) jednoprvková množina.
To úplne nesúhlasí s notáciou pre inverzné zobrazenia, kde f −1 (y) označuje priamo prvok tejto
jednoprvkovej množiny. Tieto dva objekty sa však v matematike často vzájomne zamieňajú, takže
uvedenú nejednoznačnosť nie je nutné prežívať príliš tragicky.
1
Slová
Abeceda je ľubovoľná neprázdna konečná množina. Jej prvky, ktorými môžu byť úplne ľubovoľné
objekty, nazývame symboly (znaky) alebo písmená. Slovo nad abecedou Σ je ľubovoľná konečná
postupnosť symbolov z abecedy Σ. Pri zápise takýchto postupností nepoužívame čiarky; príkladom
slova nad dvojprvkovou abecedou {a, b} tak môže byť napríklad slovo w = ababb. Prázdne slovo
(špeciálny prípad slova) je prázdna postupnosť prvkov z abecedy. V rámci tohto predmetu budeme prázdne slovo vždy označovať symbolom ε. V literatúre možno natrafiť aj na iné označenia,
napríklad λ, 1 alebo e.
Označenie prázdneho slova gréckym písmenom ε môže zvádzať k mylnému dojmu, že ε je
prvkom abecedy. Treba si však uvedomiť, že symbol ε slúži iba ako naše označenie pre prázdnu
postupnosť symbolov z abecedy, ktorá symbolom nie je.1 Čitateľ tento drobný rozpor medzi pojmom „symbol“ v zmysle definovanom vyššie a pojmom „symbol“ používaným v bežnej reči snáď
bez väčších problémov strávi.
Dĺžka slova w, označovaná symbolom |w|, je definovaná ako dĺžka postupnosti znakov, pomocou
ktorej je slovo definované. Teda ak w = a1 a2 . . . an , kde a1 , a2 , . . . , an sú symboly z nejakej abecedy,
dĺžka slova w je |w| = n. Podslovo slova w = a1 a2 . . . an je ľubovoľná súvislá podpostupnosť
postupnosti a1 a2 . . . an . Prefix slova je podslovo začínajúce prvým písmenom, sufix je podslovo
končiace posledným písmenom.
Množinu všetkých slov2 nad abecedou Σ označujeme Σ∗ , množinu všetkých neprázdnych slov
označujeme Σ+ a množinu všetkých slov dĺžky k označujeme Σk . Ako uvidíme neskôr, abeceda
je špeciálnym prípadom jazyka a uvedené označenia súhlasia s označeniami pre zodpovedajúce
operácie na jazykoch.
Notačné konvencie
Dôležitou súčasťou kultivovaného matematického prejavu je používanie notačných konvencií, ktorých cieľom je uľahčiť čitateľovi prípadne poslucháčovi jeho úlohu. Aj keď vo väčšine oblastí
matematiky existuje viacero rôznych notačných konvencií (a teória formálnych jazykov v tomto
nie je výnimkou), je nanajvýš vhodné (v prípadoch, keď neexistuje žiaden dobrý dôvod pre opak)
pridŕžať sa označení, ktoré možno považovať za „obvyklé“ . Význam notačných konvencií možno
ilustrovať na príklade definície limity postupnosti reálnych čísel {an }∞
n=0 :
lim an = L ⇐⇒ ∀ε > 0 ∃n0 ∈ N ∀n ≥ n0 : |an − L| < ε.
n→∞
To isté možno zapísať aj ako
lim a♣ = ζ 00 ⇐⇒ ∀U42 > 0 ∃ε ∈ N ∀♣ ≥ ε : |a♣ − ζ 00 | < U42 .
♣→∞
Aj keď je aj druhý zápis po formálnej stránke absolútne korektný, istý rozdiel v čitateľnosti oboch
zápisov je asi očividný.
V nasledujúcom preto zavedieme niekoľko notačných konvencií, ktorých sa budeme na týchto
cvičeniach pridŕžať. Pôjde o dohody, ktorých platnosť je ďaleko od univerzálnej a je tiež potrebné
mať na pamäti, že existujú aj situácie, kedy je vhodné a opodstatnené tieto konvencie opustiť.
• Abecedy bez ďalšej špeciálnej úlohy (v gramatike a pod.) označujeme veľkými gréckymi
písmenami Σ alebo Γ s prípadnými indexmi alebo inými „ozdobami“ , napr. Σ0 , Σ00 , Γ1 , Γ2 , . . .
• Symboly označujeme malými písmenami zo začiatku latinskej abecedy s prípadnými indexmi,
napr. a, b, c, d, a1 , a2 , . . . , an , . . .
• Slová označujeme malými písmenami z konca latinskej abecedy s prípadnými indexmi alebo
inými „ozdobami“ , napr. w, u, v, x, y, z, w0 , w00 , u1 , . . . , un , . . .
1 Bezúčelné pokusy definovať abecedu obsahujúcu prázdne slovo nad sebou samou vedú k množinovým paradoxom.
2 Alebo v terminológii, ktorú zavedieme neskôr: jazyk všetkých slov.
2
Neskôr ešte zavedieme niekoľko ďalších podobných konvencií, napríklad v súvislosti s jazykmi
alebo homomorfizmami.
Treba ale upozorniť na fakt, že napríklad naše označenie prázdneho slova symbolom ε nemožno
v žiadnom prípade považovať za notačnú konvenciu v zmysle opísanom vyššie. V tomto prípade ide
o definíciu významu priradeného danému symbolu, ktorá je platná minimálne v rámci prednášky
a cvičení k tomuto predmetu. Kým v prípade notačných konvencií nie je použitie „nekonvenčného“
symbolu chybou3 a v ojedinelých prípadoch je dokonca žiadúce, v prípade prázdneho slova je
použitie ľubovoľného označenia iného ako ε chybou v prípade, že sa toto označenie nevzťahuje
na nejakú predom uvedenú alternatívnu definíciu.
Poznámka o platnosti definícií
Podobne ako označenia, ani definície matematických objektov často nebývajú úplne ustálené. Tak
je tomu napríklad pri pojme abecedy, kde sa občas možno stretnúť aj s definíciami nevyžadujúcimi jej konečnosť alebo neprázdnosť. Podobne rôzne druhy gramatík či automatov, s ktorými sa
na tomto predmete budeme stretávať neskôr, bývajú často definované v rôznych (väčšinou v určitom zmysle ekvivalentných) obmenách, ktoré sú predovšetkým otázkou ich zamýšľaného použitia
a v neposlednom rade aj vkusu autora.
Je však dobrým zvykom v každom odbornom texte, ako aj na každej prednáške či cvičení,
predom sa dohodnúť na používaní určitých definícií a túto dohodu neskôr dodržiavať.4 V rámci
týchto cvičení sa preto všetky pojmy vzťahujú vždy iba na ich definície uvedené na prednáške,
bez ohľadu na to, či sa v literatúre vyskytuje alebo nevyskytuje alternatívna definícia.
Jazyky a množinové operácie na nich
Jazyk nad abecedou Σ je ľubovoľná množina slov nad abecedou Σ. V rámci notačnej konvencie
označujeme jazyky väčšinou symbolom L s prípadnými „ozdobami“ , napr. L, L0 , L0 , L1 , . . . Prázdny
jazyk je prázdna množina a označujeme ho symbolom ∅. Je dôležité si uvedomiť, že jazyk obsahujúci
prázdne slovo, {ε}, je iný objekt ako ∅. Jazyk je konečný, ak ide o konečnú množinu. Uveďme zopár
príkladov jazykov:
• Jazyk L1 = {a, abb, baa} je konečný jazyk nad abecedou {a, b}.
∗
• Jazyk L2 = {a, b} je jazyk nad abecedou {a, b}.
∗
• Jazyk L3 = {w ∈ {0, 1} | w je binárny zápis prvočísla} je jazyk nad abecedou {0, 1}.
• Každá abeceda je jazyk nad sebou samým.
Napríklad jazyk L1 je však súčasne aj jazyk nad abecedou {a, b, c} a podobne. Z tohto dôvodu
pre každý neprázdny jazyk L definujeme najmenšiu abecedu ΣL , nad ktorou je jazyk L. Presnejšie,
ΣL je abeceda taká, že L je jazykom nad ΣL a nie je jazykom nad žiadnou abecedou Σ ( ΣL .
Abecedu Σ∅ nemožno definovať, pretože abeceda je z definície neprázdna.
Keďže je jazyk definovaný ako množina, má zmysel zaoberať sa množinovými operáciami aplikovanými na jazyky. V tomto duchu možno definovať napríklad:
• Zjednotenie L1 ∪ L2 jazykov L1 a L2 .
• Prienik L1 ∩ L2 jazykov L1 a L2 .
• Rozdiel L1 − L2 jazykov L1 a L2 . Túto notáciu uprednostňujeme pred v matematike zaužívaným označením L1 \ L2 , ktoré sa v teórii jazykov používa pre tzv. ľavý kvocient.
• Komplement LC jazyka L. Podobne ako aj inde v matematike, komplement je nutné uvažovať
v rámci nejakého univerza. Ak nie je povedané inak, v teórii formálnych jazykov sa zväčša
ako univerzum chápe jazyk Σ∗L všetkých slov nad abecedou ΣL . Platí teda LC = Σ∗L − L.
3 Význam
symbolu totiž v takýchto situáciách nebýva definovaný predom.
prípade, že je neskôr z nejakého dôvodu treba zmeniť definíciu, je nutné na to aspoň upozorniť. Najvhodnejším
spôsobom upozornenia však vo väčšine prípadov býva nová definícia spojená so zmenou v terminológii.
4V
3
Zreťazenie
Kľúčovou operáciou je v teórii formálnych jazykov zreťazenie slov a jeho rozšírenie na jazyky.
Definícia 4. Nech Σ1 , Σ2 sú abecedy. Nech u = a1 . . . an ∈ Σ∗1 je slovo nad abecedou Σ1 a nech
v = b1 . . . bm ∈ Σ∗2 je slovo nad abecedou Σ2 . Zreťazenie slov u a v je slovo u · v nad abecedou
Σ1 ∪ Σ2 , definované ako u · v = a1 . . . an b1 . . . bm . V nasledujúcom budeme symbol · väčšinou
vynechávať a zreťazenie slov u a v označovať uv.
Zreťazenie L1 · L2 jazykov L1 a L2 je definované ako jazyk zreťazení uv všetkých dvojíc slov
u, v takých, že u ∈ L1 a v ∈ L2 .
Definícia 5. Nech L1 , L2 sú jazyky. Zreťazenie jazykov L1 a L2 je jazyk L1 · L2 definovaný ako
L1 · L2 = {uv | u ∈ L1 ; v ∈ L2 }.
Príklad 1. Uvažujme konečné jazyky L1 = {ε, a, ab, abb} a L2 = {b, ab, bb}. Jazyk L1 · L2 možno
získať nasledujúcim postupom:
1. Zapíšeme do tabuľky zreťazania všetkých dvojíc slov, kde prvé slovo je v jazyku L1 a druhé
slovo je v jazyku L2 .
b
ab
bb
ε
b
ab
bb
a
ab
aab
abb
ab abb abab abbb
abb abbb abbab abbbb
2. Jazyk L1 ·L2 obsahuje všetky zreťazenia získané postupom z bodu 1. Po odstránení duplikátov
teda dostávame
L1 · L2 = {b, ab, bb, aab, abb, abab, abbb, abbab, abbbb}.
Mocnina slova a jazyka
Mocnina slova aj mocnina jazyka sa definujú bežným spôsobom vzhľadom na operáciu zreťazenia.
Definícia 6. Nech w je slovo. Potom w0 = ε a wn+1 = wn w pre všetky n ∈ N.
Definícia 7. Nech L je jazyk. Potom L0 = {ε} a Ln+1 = Ln · L pre všetky n ∈ N.
Nulté mocniny sú v oboch prípadoch definované prirodzeným spôsobom ako neutrálny prvok
vzhľadom na danú operáciu zreťazenia – čitateľ ľahko overí, že pre všetky slová w a všetky jazyky
L skutočne platí εw = wε = w a {ε} · L = L · {ε} = L.
Dokážeme teraz, že jazyk Ln pozostáva zo zreťazení všetkých n-tíc slov z jazyka L.
Tvrdenie 1. Nech L je jazyk a n ∈ N. Potom Ln = {w1 . . . wn | w1 , . . . , wn ∈ L}.
Dôkaz. Indukciou vzhľadom na n.
1. Pre n = 0 je tvrdenie triviálne.
2. Nech tvrdenie platí pre n = k. Ukážeme, že platí aj pre n = k + 1. Skutočne,
Lk+1 = Lk · L = {w1 . . . wk | w1 , . . . , wk ∈ L} · L = {w1 . . . wk+1 | w1 , . . . , wk+1 ∈ L},
kde prvá rovnosť je z definície 7, druhá rovnosť vyplýva z indukčného predpokladu a posledná
rovnosť je z definície 5.
Tvrdenie je dokázané.
Častou chybou u študentov býva zamieňanie si n-tej mocniny jazyka L s jazykom n-tých mocnín
slov z jazyka L. Čitateľ určite ľahko dokáže, že vo všeobecnosti Ln 6= {wn | n ∈ N}.
Aj keď význam výrazov typu 00 je v matematike pomerne diskutabilný, v teórii jazykov je
zvykom definovať ∅0 = {ε}, čo koniec koncov vyplýva aj z definície 7. Ide tu o určitú analógiu
(dobre odôvodnenej) konvencie 00 = 1, ktorá sa používa v niektorých oblastiach matematiky.
4
Iterácia a kladná iterácia
Definícia 8. Nech L je jazyk. Iterácia jazyka L je jazyk
L∗ =
∞
[
Lk
k=0
a kladná iterácia jazyka L je jazyk
+
L =
∞
[
Lk .
k=1
Operácia iterácie sa zvykne nazývať aj uzáver alebo Kleeneho hviezdička a operácia kladnej iterácie
sa nazýva aj kladný uzáver alebo Kleeneho plus.
Ako už čitateľ iste tuší, vyššie zavedené označenia Σ∗ a Σ+ pre abecedu Σ súhlasia s uvedenou
definíciou. Vyplýva to z nasledujúceho tvrdenia.
Tvrdenie 2. Nech L je jazyk. Pre jeho iteráciu platí L∗ = {w1 , . . . , wk | k ∈ N; w1 , . . . , wk ∈ L}
a pre jeho kladnú iteráciu platí L+ = {w1 , . . . , wk | k ∈ N; k ≥ 1; w1 , . . . , wk ∈ L}.
Dôkaz. Ak rozpíšeme Lk podľa tvrdenia 1, dostávame pre iteráciu
∞
[
L∗ =
∞
[
Lk =
{w1 . . . wk | w1 , . . . , wk ∈ L} = {w1 , . . . , wk | k ∈ N; w1 , . . . , wk ∈ L}
k=0
k=0
a pre kladnú iteráciu
L+ =
∞
[
Lk =
k=1
∞
[
{w1 . . . wk | w1 , . . . , wk ∈ L} = {w1 , . . . , wk | k ∈ N; k ≥ 1; w1 , . . . , wk ∈ L},
k=1
čo bolo treba dokázať.
∗
∗
Úloha 1. Zistite, či vo všeobecnosti5 platí (L1 ∪ L2 ) = L∗1 · (L2 · L∗1 ) . Svoje tvrdenie dokážte.
Riešenie. Ukážeme, že tvrdenie platí. Postupne teda dokážeme obidve inklúzie:
∗
⊆: Nech w ∈ (L1 ∪ L2 ) . Potom podľa tvrdenia 2 existuje k ∈ N a slová w1 , . . . , wk ∈ L1 ∪ L2
tak, že w = w1 . . . wk . Nech 1 ≤ i1 < . . . < is ≤ k sú indexy také, že wi1 , . . . , wis sú práve
všetky slová spomedzi w1 , . . . , wk , ktoré sú v L2 . Zvyšné zo slov w1 , . . . , wk preto musia byť
v L1 , a teda všetky slová
u0 = w1 w2 . . . wi1 −1 ,
u1 = wi1 +1 wi1 +2 . . . wi2 −1 ,
...,
us = wis +1 wis +2 . . . wk
musia byť podľa tvrdenia 2 v L∗1 (niektoré z týchto slov môžu byť aj prázdne). Pre j = 1, . . . , s
∗
teda platí wij uj ∈ L2 · L∗1 , z čoho podľa tvrdenia 2 vyplýva wi1 u1 . . . wis us ∈ (L2 · L∗1 ) .
Zrejme platí
w = u0 wi1 u1 . . . wis us ,
∗
pričom vieme, že u0 ∈ L∗1 a wi1 u1 . . . wis us ∈ (L2 · L∗1 ) . Z definície zreťazenia jazykov teda
∗
vyplýva w ∈ L∗1 · (L2 · L∗1 ) , čo bolo treba dokázať.
∗
⊇: Nech w ∈ L∗1 · (L2 · L∗1 ) . Z definície zreťazenia jazykov a tvrdenia 2 vyplýva w = u0 v1 . . . vk ,
kde u0 ∈ L∗1 a v1 , . . . , vk ∈ L2 · L∗1 . Keďže u0 ∈ L∗1 , z tvrdenia 2 vyplýva u0 = x0,1 . . . x0,j0
pre nejaké slová x0,1 , . . . , x0,j0 ∈ L1 ⊆ L1 ∪ L2 . Keďže pre i = 1, . . . , k platí vi ∈ L2 · L∗1 ,
z definície zreťazenia jazykov a tvrdenia 2 vyplýva, že vi = yi xi,1 . . . xi,ji pre nejaké slová
yi , xi,1 , . . . , xi,ji ∈ L1 ∪ L2 . Platí teda
w = x0,1 . . . x0,j0 y1 x1,1 . . . x1,j1 . . . yk xk,1 . . . xk,jk ,
kde všetky slová xi,j a yi (i = 0, . . . , k, j = 1, . . . , ji ) sú v L1 ∪ L2 . Z tvrdenia 2 teda vyplýva
∗
w ∈ (L1 ∪ L2 ) , čo bolo treba dokázať.
Tvrdenie je dokázané.
5 Teda
pre ľubovoľné dva jazyky L1 , L2 .
5
Homomorfizmus
Pod pojmom homomorfizmus sa v matematike chápe štruktúru zachovávajúce zobrazenie (kde pod
štruktúrou možno rozumieť napr. grupovú štruktúru, vektorovú štruktúru6 a pod.). Štruktúra
slov nad abecedou Σ je daná predovšetkým operáciou zreťazenia a pod homomorfizmom teda
rozumieme zobrazenie, ktoré túto operáciu zachováva.
Definícia 9. Nech Σ, Γ sú abecedy a h : Σ∗ → Γ∗ je zobrazenie. Zobrazenie h sa nazýva homomorfizmus zo Σ∗ do Γ∗ , ak pre všetky u, v ∈ Σ∗ platí
h(uv) = h(u)h(v).
Ak navyše pre každé w ∈ Σ+ platí h(w) ∈ Γ+ , nazýva sa homomorfizmus h nevymazávajúci.
Neskôr ukážeme, že takto definovaný homomorfizmus je v skutočnosti homomorfizmom monoidov. V rámci notačnej konvencie budeme homomorfizmy väčšinou označovať symbolom h s prípadnými indexmi alebo inými „ozdobami“ .
V nasledujúcich dvoch tvrdeniach postupne dokážeme, že homomorfný obraz prázdneho slova
je vždy prázdne slovo a že každý homomorfizmus je jednoznačne určený obrazmi písmen.
Tvrdenie 3. Nech Σ, Γ sú abecedy a h : Σ∗ → Γ∗ je homomorfizmus. Potom h(ε) = ε.
Dôkaz. Sporom. Nech h(ε) = x pre nejaké x ∈ Γ+ . Potom pre každé u ∈ Σ∗ z definície homomorfizmu vyplýva
h(u) = h(uε) = h(u)h(ε) = h(u)x,
čo je spor, keďže rovnosť h(u) = h(u)x nemôže platiť pre žiadne neprázdne slovo x.
Tvrdenie 4. Nech Σ, Γ sú abecedy a h : Σ∗ → Γ∗ je homomorfizmus. Nech h0 : Σ∗ → Γ∗ je
homomorfizmus taký, že pre všetky c ∈ Σ platí h0 (c) = h(c). Potom h0 = h.
Dôkaz. Treba dokázať, že pre všetky w ∈ Σ∗ platí h0 (w) = h(w). Z tvrdenia 3 a predpokladu na
homomorfizmus h0 vyplýva, že rovnosť platí pre všetky w také, že |w| ≤ 1. Nech teraz |w| = k > 1.
Potom w = a1 . . . ak pre nejaké a1 , . . . , ak ∈ Σ. Matematickou indukciou by sme ľahko dokázali,
že z definície homomorfizmu vyplýva h(w) = h(a1 ) . . . h(ak ) a h0 (w) = h0 (a1 ) . . . h0 (ak ). Keďže ale
pre všetky c ∈ Σ platí h0 (c) = h(c), z uvedených dvoch rovností vyplýva h0 (w) = h(w), čo bolo
treba dokázať.
Obraz jazyka L pri zobrazení homomorfizmom h je jednoducho obraz množiny L pri zobrazení
h v zmysle definície 1.
Definícia 10. Nech Σ, Γ sú abecedy, h : Σ∗ → Γ∗ je homomorfizmus a L ⊆ Σ∗ je jazyk. Obraz
jazyka L pri zobrazení homomorfizmom h je jazyk h(L) = {h(w) | w ∈ L}.
Úloha 2. Nech L1 , L2 sú jazyky a h je ľubovoľný vhodný homomorfizmus. Porovnajte navzájom
jazyky h(L1 ∪ L2 ) a h(L1 ) ∪ h(L2 ).7
Riešenie. Dokážeme, že platia obidve inklúzie, a teda h(L1 ∪ L2 ) = h(L1 ) ∪ h(L2 ).
⊆: Nech u ∈ h(L1 ∪ L2 ). Z definície 10 vyplýva, že existuje v ∈ L1 ∪ L2 také, že u = h(v). Keďže
v ∈ L1 ∪ L2 , musí platiť v ∈ L1 alebo v ∈ L2 (alebo oboje). Ak v ∈ L1 , u = h(v) ∈ h(L1 ).
Ak v ∈ L2 , u = h(v) ∈ h(L2 ). Keďže ale h(L1 ), h(L2 ) ⊆ h(L1 ) ∪ h(L2 ), v oboch prípadoch
máme u ∈ h(L1 ) ∪ h(L2 ).
⊇: Nech u ∈ h(L1 ) ∪ h(L2 ). Potom u ∈ h(L1 ) alebo u ∈ h(L2 ). Bez ujmy na všeobecnosti, nech
u ∈ h(L1 ). Potom z definície 10 vyplýva, že existuje v ∈ L1 také, že u = h(v). Keďže v ∈ L1 ,
platí aj v ∈ L1 ∪ L2 . Preto u = h(v) ∈ h(L1 ∪ L2 ), čo bolo treba dokázať.
Tvrdenie je dokázané.
6 Homomorfizmy
medzi vektorovými priestormi sú známe skôr ako lineárne zobrazenia.
„vhodným“ homomorfizmom rozumieme ľubovoľný homomorfizmus, pre ktorý sú obrazy h(L1 ), h(L2 ) a
h(L1 ∪ L2 ) dobre definované, t.j. ľubovoľný homomorfizmus h : Σ∗ → Γ∗ , kde ΣL1 ∪ ΣL2 ⊆ Σ. Porovnať dvojicu
jazykov znamená určiť, či (pre ľubovoľné L1 , L2 a h) platia relácie ⊆ a ⊇. Ak pre nejaké dva jazyky neplatí žiadna
z týchto relácií, nazývajú sa tieto jazyky neporovnateľné.
7 Pod
6
Inverzný homomorfizmus
Inverzný homomorfizmus je inverzný obraz v zmysle definícií 2 a 3, kde príslušné zobrazenie je
homomorfizmus.
Definícia 11. Nech Σ, Γ sú abecedy, h : Σ∗ → Γ∗ je homomorfizmus a L ⊆ Γ∗ je jazyk. Obraz
jazyka L pri zobrazení inverzným homomorfizmom h−1 je jazyk h−1 (L) = {u ∈ Σ∗ | h(u) ∈ L}.
Definícia 12. Nech Σ, Γ sú abecedy, h : Σ∗ → Γ∗ je homomorfizmus a v ∈ Γ∗ je slovo. Obraz
slova v pri zobrazení inverzným homomorfizmom h−1 je jazyk
h−1 (v) = h−1 ({v}) = {u ∈ Σ∗ | h(u) ∈ {v}} = {u ∈ Σ∗ | h(u) = v}.
O niečo presnejšie by bolo namiesto o „obraze pri zobrazení inverzným homomorfizmom h−1 “
hovoriť o „inverznom obraze pri homomorfizme h“ , prípadne o „inverznom homomorfnom obraze“ .
Jedná sa však o zaužívanú terminológiu súvisiacu s predstavou inverzného homomorfizmu ako
∗
zobrazenia h−1 : Γ∗ → 2Σ .
Príklad 2. Ilustrujme ešte definíciu inverzného homomorfizmu na príklade. Nech Σ = {a, b, c},
Γ = {a, b} a h je homomorfizmus definovaný8 ako h(a) = ab, h(b) = a a h(c) = ab. Potom napríklad
h−1 (aab) = {ba, bc} a h−1 (b) = h−1 (bb) = ∅. V dôsledku toho napríklad pre L = {b, aab} platí
h−1 (L) = {ba, bc}.
* Voľný monoid
Zreťazenie slov je zjavne asociatívne a ε je neutrálny prvok vzhľadom na túto operáciu. Pre každú
abecedu Σ tak jazyk Σ∗ tvorí s operáciou zreťazenia tzv. voľný monoid nad Σ.9
Definícia 13. Grupoid je usporiadaná dvojica (X, ◦), kde X je množina a ◦ : X × X → X je
binárna operácia na X. Pologrupa je grupoid, pre ktorý navyše platí:
(i) Asociatívnosť: ∀x, y, z ∈ X : x ◦ (y ◦ z) = (x ◦ y) ◦ z.
Pologrupa s jednotkou alebo monoid je pologrupa, pre ktorú navyše platí:
(ii) Existencia neutrálneho prvku: ∃eX ∈ X ∀x ∈ X : x ◦ eX = eX ◦ x = x.
Grupa je monoid, pre ktorý navyše platí:
(iii) Existencia inverzných prvkov: ∀x ∈ X ∃x−1 ∈ X : x ◦ x−1 = x−1 ◦ x = eX .
Tvrdenie 5. Nech Σ je abeceda. Potom (Σ∗ , ·) je monoid, ktorý sa nazýva voľný monoid nad
abecedou Σ.
Dôkaz. Zrejmé z definície zreťazenia.
Homomorfizmus medzi monoidmi (X, ◦) a (Y, •) je ľubovoľné zobrazenie h : X → Y spĺňajúce
h(x ◦ y) = h(x) • h(y) pre všetky x, y ∈ X a h(eX ) = eY . Homomorfizmus slov h : Σ∗ → Γ∗ by sme
teda mohli definovať jednoducho ako homomorfizmus medzi monoidmi (Σ∗ , ·) a (Γ∗ , ·).
Zvyčajná definícia voľného monoidu je ale o niečo všeobecnejšia. Kľúčová je pri takejto definícii
vlastnosť homomorfizmov slov, ktorú sme sformulovali ako tvrdenie 4: každý homomorfizmus je
jednoznačne určený obrazmi písmen z abecedy. Formálne potom definujeme voľný monoid (X, ◦)
nad podmnožinou X 0 ⊆ X nasledovne.
Definícia 14. Nech (X, ◦) je monoid a X 0 ⊆ X. Monoid (X, ◦) je voľný nad X 0 , ak pre každý
monoid (Y, •) a každé zobrazenie f : X 0 → Y existuje práve jeden homomorfizmus h : X → Y taký,
že pre všetky x ∈ X 0 platí h(x) = f (x).
8 Podľa
tvrdenia 4 je postačujúce definovať homomorfizmus pomocou obrazov písmen z abecedy Σ.
9 http://en.wikipedia.org/wiki/Free_monoid
7
Dá sa dokázať, že ľubovoľný monoid voľný nad Σ v zmysle definície 14 je izomorfný s voľným
monoidom (Σ∗ , ·).
Monoid nie je jedinou algebraickou štruktúrou, pre ktorú sa dá definovať vlastnosť voľnosti.
Analogicky k voľným monoidom by sa dala definovať napríklad voľná pologrupa. V skutočnosti
je voľnosť dokonca tzv. univerzálna vlastnosť, čiže vlastnosť, ktorá sa pomocou teórie kategórií
definuje konzistentne pre všetky druhy algebraických štruktúr.
* Polokruh formálnych jazykov
∗
Nech Σ je abeceda. Množina 2Σ všetkých formálnych jazykov nad abecedou Σ tvorí s aditívnou
operáciou zjednotenia a multiplikatívnou operáciou zreťazenia polokruh, čo je algebraická štruktúra definovaná nasledovne:
Definícia 15. Polokruh je usporiadaná trojica (S, +, ·), kde S je množina, + : S × S → S a
· : S × S → S sú binárne operácie na S a kde platí:
(i) (S, +) je komutatívny monoid s neutrálnym prvkom 0S .
(ii) (S, ·) je monoid s neutrálnym prvkom 1S .
(iii) Platia distributívne zákony: ∀x, y, z ∈ S : (x + y) · z = x · z + y · z a z · (x + y) = z · x + z · y.
(iv) Pre každé x ∈ S platí x · 0S = 0S · x = 0S .
Poznámka 1. Takto definovaná štruktúra sa niekedy nazýva aj polokruh s jednotkou, pričom u všeobecného polokruhu sa nepožaduje existencia multiplikatívneho neutrálneho prvku (teda v podmienke (ii) sa iba vyžaduje, aby (S, ·) bola pologrupa).10 V teoretickej informatike sa však takmer
výhradne používa horeuvedená definícia.
∗
Tvrdenie 6. Nech Σ je abeceda. Potom (2Σ , ∪, ·) je polokruh nazývaný polokruh formálnych
jazykov nad Σ, s aditívnym neutrálnym prvkom ∅ a multiplikatívnym neutrálnym prvkom {ε}.
Dôkaz. Prenechávame čitateľovi ako elementárne cvičenie.
Homomorfizmus medzi polokruhmi (S, +S , ·S ), (T, +T , ·T ) je ľubovoľné zobrazenie h : S → T
také, že h(0S ) = 0T , h(1S ) = 1T a pre všetky x, y ∈ S platí h(x +S y) = h(x) +T h(y) a
∗
∗
h(x ·S y) = h(x) ·T h(y). Ak homomorfizmus jazykov chápeme ako zobrazenie h : 2Σ → 2Γ , je
takto definované zobrazenie aj homomorfizmom v polokruhu formálnych jazykov. To platí vďaka
identite h(L1 ∪L2 ) = h(L1 )∪h(L2 ) dokázanej v úlohe 2 a vďaka identite h(L1 ·L2 ) = h(L1 )·h(L2 ),
ktorej dôkaz je jednou z úloh určených na nasledujúce cvičenie.
10 Rovnaká
situácia je aj pri definíciách okruhu.
8
Download

Poznámky k cvičeniu č. 1 - Formálne jazyky a automaty