Univerzita Karlova v Praze
Matematicko-fyzikální fakulta
BAKALÁSKÁ PRÁCE
Josef Tkadlec
Separace slov pomocí jazyk· Katedra algebry
Vedoucí bakalá°ské práce:
Studijní program:
Studijní obor:
doc. Mgr. t¥pán Holub, Ph.D.
Matematika
Obecná matematika
Praha 2012
Na tomto míst¥ bych rád pod¥koval své rodin¥ za podporu b¥hem psaní této práce jakoº i b¥hem celého studia a svému vedoucímu doc. t¥pánu Holubovi za jeho nezm¥rnou trp¥livost a mnoho cenných post°eh·.
Prohla²uji, ºe jsem tuto bakalá°skou práci vypracoval samostatn¥ a výhradn¥ s pouºitím citovaných pramen·, literatury a dal²ích odborných zdroj·. Beru na v¥domí, ºe se na moji práci vztahují práva a povinnosti vyplývající ze zákona £. 121/2000 Sb., autorského zákona v platném zn¥ní, zejména skute£nost, ºe Univerzita Karlova v Praze má právo na uzav°ení licen£ní smlouvy o uºití této práce jako ²kolního díla podle 60 odst. 1 autorského zákona.
V ........ dne ............
Podpis autora
Název práce: Separace slov pomocí jazyk· Autor: Josef Tkadlec Katedra: Katedra algebry Vedoucí bakalá°ské práce: doc. Mgr. t¥pán Holub, Ph.D., Katedra algebry Abstrakt: V této práci se zabýváme rozklady jazyka v²ech kone£ných slov nad danou abecedou
A
na
n
komutativních jazyk·, které separují
n
p°edem daných
slov a jsou uzav°ené vzhledem ke konkatenaci. V první £ásti de nujeme pot°ebné pojmy z kombinatoriky na slovech. Ve druhé £ásti nejd°íve ukazujeme, ºe hledaný rozklad existuje práv¥ tehdy, kdyº má kaºdá dvojice separovaných slov lineárn¥ nezávislé Parikhovy obrazy, a charakterizujeme v²echny takové rozklady nad dvouprvkovou abecedou. Následn¥ ukazujeme, ºe p°i vynechání poºadavku na komutativitu jazyk· lze slova separovat práv¥ tehdy, kdyº ºádná dv¥ nekomutují. K posledn¥ jmenovanému tvrzení podáváme dva odli²né d·kazy. Klí£ová slova: kombinatorika na slovech, komutativní jazyky, Parikhovo zobrazení, separace uzav°enými mnoºinami
Title: Separation of words by languages Author: Josef Tkadlec Department: Department of Algebra Supervisor: doc. Mgr. t¥pán Holub, Ph.D., Department of Algebra Abstract: In this work we consider the partitions of the language of all nite words over the given nite alphabet
n
A
into
n
commutative languages which separate
given words and are closed with respect to concatenation. In the rst part we
de ne the necessary notions from combinatorics on words. In the second part we prove that such partition exists if and only if the Parikh images of the words are pairwise linearly independent and we characterize all such partitions over twoelement alphabet. Next we show that if we omit the condition of commutativity of the languages, the words can be separated if and only if they pairwise do not commute. We present two dierent proofs of the latter claim. Keywords: combinatorics on words, commutative languages, Parikh map, separation by closed sets
Obsah
Seznam pouºitých zkratek
2
Úvod
3
1 Základy kombinatoriky na slovech
4
1.1
Kombinatorika na slovech
. . . . . . . . . . . . . . . . . . . . . .
4
1.2
Komutativita v kombinatorice na slovech . . . . . . . . . . . . . .
5
2 Separace slov pomocí jazyk·
6
2.1
Problém . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
Komutativní jazyky . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3
Geometrický p°ístup
2.4
Binární p°ístup
. . . . . . . . . . . . . . . . . . . . . . . . .
13
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
Záv¥r
19
Seznam pouºité literatury
20
1
Seznam pouºitých zkratek N N+
nezáporná celá £ísla kladná celá £ísla
Q
racionální £ísla
R
reálná £ísla
k
k -rozm¥rný
R
[a1 , . . . , ak ] (an an−1 . . . a0 )2
eukleidovský prostor
bod kartézské soustavy sou°adnic o sou°adnicích £íslo zapsané ve dvojkové soustav¥, tedy
2
Pn
i=0
a1 , . . . , a k
ai 2i
Úvod Kombinatorika na slovech je odv¥tví prostupující mnoha r·znými obory. Krom¥ formální lingvistiky a teorie automat· úzce souvisí i s kombinatorickou teorií £ísel £i lineární algebrou. Jedním z velmi £astých koncept· v matematice je koncept uzav°enosti mnoºiny vzhledem k n¥jaké operaci. V kontextu kombinatoriky na slovech je p°irozeným kandidátem pro tuto operaci takzvaná konkatenace (£ili slepování slov). V roce 2011 se v £lánku [1] pánové Brzozowski, Grant a Shallit zabývali otázkou, zda pro daná dv¥ slova nad danou abecedou existuje rozklad v²ech slov nad touto abecedou na dv¥ uzav°ené mnoºiny, které budou odd¥lovat ona dv¥ p·vodní slova. Ukázali, ºe takový rozklad existuje práv¥ tehdy, kdyº p°edepsaná dv¥ slova nekomutují. Pozd¥ji v témºe roce v £lánku [2] pánové Holub a Kortelainen zobecnili toto tvrzení i pro více slov neº dv¥. V této práci shrnujeme jejich výsledky a p°idáváme n¥které dal²í.
V první £ásti práce de nujeme jen ty nejzákladn¥j²í pojmy kombinatoriky na slovech, bez kterých se v dal²ím výkladu neobejdeme. tená°e baºícího po ²ir²ím rozhledu odkazujeme na [3] p°ípadn¥ na [4]. Ve druhé £ásti formulujeme problém separace slov pomocí uzav°ených jazyk·, jímº se zabýváme po zbytek práce. Nejd°íve problém vy°e²íme v kontextu komutativních jazyk· tím, ºe dokáºeme domn¥nku z £lánku [2]. Poskytneme navíc charakteristiku rozklad· na dva uzav°ené jazyky nad dvouprvkovou abecedou. Následn¥ rozvineme a zobecníme my²lenky z £lánku [1], £ímº podáme °e²ení problému i pro obecn¥ nekomutativní jazyky. Na samotný záv¥r pak p°edstavíme alternativní °e²ení téhoº problému, které bylo popsáno op¥t v £lánku [2].
3
1. Základy kombinatoriky na slovech 1.1
Kombinatorika na slovech
De nice. Abecedou
rozumíme neprázdnou kone£nou mnoºinu symbol·. T¥m-
to symbol·m °íkáme
písmena. Slovem w
nad abecedou
A
rozumíme kone£nou
posloupnost písmen
a1 , . . . , an ∈ A.
w = (a1 , a2 , . . . , an ), P°ipou²tíme i
n = 0,
Mnoºinu v²ech slov nad abecedou slov nad abecedou
prázdné slovo, které
£emuº odpovídá
e.
A zna£íme A∗ . Mnoºinu v²ech neprázdných
A zna£íme A+ = A∗ \{e}. Jazykem rozumíme libovolnou (tedy
i nekone£nou) neprázdnou podmnoºinu
De nice.
zna£íme
Mnoºina
A∗
A∗ .
je p°irozen¥ vybavena binární operací
de novanou jako
◦ : A∗ × A∗ → A∗
(a1 , a2 , . . . , an ) ◦ (b1 , b2 , . . . , bm ) = (a1 , a2 , . . . , an , b1 , b2 , . . . , bm ). Tuto operaci nazýváme Místo
w = u◦v
konkatenace, p°ípadn¥ sou£in.
pí²eme zpravidla jen
w = uv .
Jelikoº
(a1 , a2 , . . . , an ) = (a1 ) ◦
(a2 )◦· · ·◦(an ) budeme podobn¥ namísto w = (a1 , a2 , . . . , an ) psát w = a1 a2 . . . an . Pro kaºdé slovo
vzhledem k operaci
De nice. |w| = n
A´
slova
w ∈ A∗
◦,
platí
trojice
(A∗ , ◦, e)
w = a1 a2 . . . an w
w ◦ e = w = e ◦ w.
Pro
a∈A
je monoid a dvojice
e
je proto neutrální
(A+ , ◦)
je neprázdné slovo nad abecedou
je pologrupa.
A.
Pak
délkou
rozumíme po£et písmen, z nichº se skládá. Délku prázdného
slova klademe rovnu nule. Zobrazení homomor smus
Prvek
∗
(A , ◦, e)
a
(N, +, 0).
zna£íme symbolem
|w| =
X a∈A
ϕ : w ∈ A∗ 7→ |w| ∈ N
|w|a
|w|a
je z°ejm¥ monoidový
po£et výskyt· písmene
a
ve slov¥
w.
Platí
|uv|a = |u|a + |v|a .
a
De nice. A´ u = a1 a2 . . . an , v = b1 b2 . . . bm jsou slova nad abecedou A. ekneme, ºe
u
je
pre xem
Symbolem
wA∗
u, w
v,
jestliºe
n ≤ m
a pro kaºdé
i = 1, . . . , n
zna£íme jazyk t¥ch slov, která mají za pre x slovo
Poznámka 1.1. slov
slova
Spl¬ují-li slova
u, v, w, z
je pre xem toho druhého.
4
rovnost
uv = wz ,
je
ai = b i .
w.
pak alespo¬ jedno ze
1.2
Komutativita v kombinatorice na slovech
De nice.
M¥jme
k ∈ N+
rozumíme zobrazení
a abecedu
Ψ : A∗ → Nk ,
A = {a1 , . . . , ak }. Parikhovým zobrazením
které slovu
w ∈ A∗
p°i°adí vektor
Ψ(w) = (|w|a1 , . . . , |w|ak ) .
Parikh·v obraz slova w. ekneme, ºe jazyk L nad abecedou A je komutativní, jestliºe pro kaºdé w1 ∈ L
Vektoru
a
Ψ(w)
w2 ∈ A ∗
°íkáme
takové, ºe
Ψ(w2 ) = Ψ(w1 ),
Parikhovým obrazem jazyka L
Pro podmnoºinu
L
k
S⊆N
je i
A´
A
Ψ(L) = {Ψ(w) | w ∈ L}.
p°irozen¥ rozumíme
naopak klademe
je tedy komutativní práv¥ tehdy, kdyº
De nice.
w2 ∈ L. −1
Ψ (S) = {w ∈ A∗ | Ψ(w) ∈ S}. Jazyk
Ψ−1 (Ψ(L)) = L.
u, v ∈ A∗ komutují,
je abeceda. ekneme, ºe slova
jestliºe
uv = vu. Na samý záv¥r této £ásti je²t¥ p°ipomeneme standardní kombinatoricko-slovní lemma.
Lemma 1.2.
A´
existuje slovo
r ∈ A+
D·kaz:
A
je abeceda a
Jsou-li slova
rb ra = vu,
a exponenty
u, v
Pak
a, b ∈ N+
písmen slov
uv = vu
získáváme
slova. To platí speciáln¥ i pro obecnosti p°edpokládejme, ºe Jelikoº
v
je pre xem
toto slovo
w
platí
Je-li
u,
mocninou téhoº slova
r.
v
u
Slovo
u
a
Dále a´
existuje neprázdné slovo
u = wv .
|vw| = |u| < |uv|,
u = ra pak
v = rb .
a
uv = ra rb = ra+b =
pak porovnáním prvních
|u| > |v|.
takºe
komutují práv¥ tehdy, kdyº
komutují.
a tedy
|u| = |v| = 1.
vu = uv = vwv ,
Protoºe jsou neprázdná a
|u| = |v|,
u = v,
a
r ∈ A+ ,
u, v
takºe skute£n¥ komutují. Nyní a´
|uv|.
u
takové, ºe
mocninou téhoº slova
Postupujme indukcí podle
|v|
u, v ∈ A+ .
w
v
|u| =
jsou mocninami téhoº
|uv| > 2
a bez újmy na
takové, ºe
Slova
v
a
w
u = vw.
Pro
tak komutují.
jsou díky induk£nímu p°edpokladu
je pak z°ejm¥ rovn¥º mocninou
u
r.
v w
v
u
Obrázek 1.1: Kombinatoricko-slovní lemma Nyní se m·ºeme bez obav pustit do st¥ºejního tématu této práce, totiº do zkoumání rozklad· jazyka na uzav°ené jazyky.
5
2. Separace slov pomocí jazyk· 2.1
Problém
De nice.
A
A´
kaºdá dv¥ slova A´
n ∈ N
mnoºiny
je abeceda. ekneme, ºe jazyk
u, v ∈ L
a
je i
uv ∈ L.
L1 , . . . , Ln ⊆ A+ .
L ⊆ A+
ekneme, ºe
je
uzav°ený,
n-tice {Li }ni=1
jestliºe pro
tvo°í
rozklad
A+ , jestliºe L1 , . . . , Ln jsou navzájem disjunktní neprázdné jazyky takové,
ºe
A+ =
n [
Li .
i=1 ekneme, ºe tento rozklad je
uzav°ený,
pokud jsou v²echny jazyky
L1 , . . . , Ln
uzav°ené. Kone£n¥ °ekneme, ºe uzav°ený rozklad z mnoºiny takové, ºe
{Li }ni=1 separuje n-tici slov w1 , . . . , wn
A+ , jestliºe pro kaºdé i = 1, . . . , n existuje práv¥ jedno j ∈ {1, 2, . . . , n} wj ∈ Li .
P°edchozí de nice dává prostor ke zkoumání toho, kolik uzav°ených rozklad· existuje. Neº se této otázce za£neme v¥novat blíºe, uve¤me n¥kolik elementárních p°íklad· uzav°ených rozklad·.
P°íklady 1.
Uvaºme dvouprvkovou abecedu
abb. (i) Jazyky
K1 = a+ = {a, aa, aaa, . . . }
mnoºiny
a
A+ .
A = {a, b}
K2 = L \ K1
a slova
w1 = aab, w2 =
tvo°í uzav°ený rozklad
(ii) Jazyky
L1 =
1 w ∈ A |w|a ≥ |w| 2 +
tvo°í uzav°ený rozklad mnoºiny
a
A+
separující slova
(iii) Jazyky
M1 = aA∗ , M2 = bA∗
(iv) Jazyky
N1 = {a} ∪ aaA∗ , N2 = bA∗ ∪ abA∗
slova
1 + L2 = w ∈ A |w|a < |w| 2 w1 , w2 .
tvo°í uzav°ený rozklad mnoºiny
A+ .
tvo°í uzav°ený rozklad separující
w1 , w2 .
D·kaz: Snadno se p°esv¥d£íme, ºe ve v²ech p°ípadech se jedná o rozklady mnoºiny
A+ .
Ukáºeme, ºe v²echny pouºité jazyky jsou uzav°ené.
6
K1
(i) Jazyk
jist¥ uzav°ený je. V²imn¥me si, ºe
Jelikoº pro
u, v ∈ K2
platí
K2 = {w ∈ A+ | |w|b ≥ 1}.
|uv|b = |u|b + |v|b ≥ 1 + 1 ≥ 1, je i
K2
uzav°ený.
(ii) Pro kaºdá dv¥ slova
u, v ∈ L1
platí
1 1 1 |uv|a = |u|a + |v|a ≥ |u| + |v| = |uv|, 2 2 2 takºe
L1
w1 ∈ L1
je uzav°ený. Analogicky ukáºeme, ºe i a
L2
je uzav°ený. Navíc jist¥
w2 ∈ L2 .
(iii) Sou£inem slov za£ínajících na totéº písmeno je slovo za£ínající op¥t na totéº písmeno, takºe
M1 i M2
jsou uzav°ené.
(iv) Sou£inem slov, z nichº kaºdé má n¥který sv·j pre x v jisté mnoºin¥ op¥t slovo s n¥kterým svým pre xem náleºejícím a
S.
Navíc z°ejm¥
w2 ∈ N2 .
S,
je
w1 ∈ N1
n-tici
Na²ím cílem bude pro zadanou
slov
n existuje uzav°ený rozklad {Li }i=1 mnoºiny
+
A
w1 , . . . , w n ∈ A +
rozhodnout, zda
, který ji separuje. Za£neme snad-
ným lemmatem.
Lemma 2.1.
Pokud neprázdná slova
uzav°ené jazyky D·kaz:
takové, ºe
P°edpokládejme, ºe
Jelikoº slova existují
L1 , L2
uav
α, β ∈ N+
u, v
u ∈ L1
u ∈ L1
a
a
komutují, pak neexistují disjunktní
v ∈ L2 .
v ∈ L2 ,
kde
L1
a
L2
jsou uzav°ené jazyky.
komutují, jsou díky Lemmatu 1.2 mocninou téhoº slova taková, ºe
u=r
α
,
v=r
β
. Z uzav°enosti
L1 , L2
r, tedy
ov²em plyne
L1 3 uβ = rαβ = rβα = v α ∈ L2 , takºe jazyky
L1 , L2
D·sledek 2.2.
nejsou disjunktní.
Nelze separovat
n-tici
slov
w1 , . . . , wn ∈ A+ ,
v níº n¥která dv¥
slova komutují. D·kaz:
Skute£n¥, taková dv¥ slova díky p°edchozímu lemmatu nemohou leºet
v r·zných jazycích, protoºe ty jsou uzav°ené a disjunktní.
Ukazuje se, ºe podmínka na nekomutativitu dvojic slov je nejen nutná, ale i posta£ující. Platí totiº následující v¥ta.
7
V¥ta 2.3.
A´
n∈N
a
w1 , . . . , w n
ºe pro kaºdou dvojici index·
jsou neprázdná slova nad abecedou
i, j ∈ {1, . . . , n}, i 6= j ,
n Pak existuje uzav°ený rozklad {Li }i=1 mnoºiny
A+
slova
wi
a
wj
separující slova
A
taková,
nekomutují.
w1 , . . . , w n .
Práv¥ zmín¥nou v¥tu dokáºeme pozd¥ji. Nejd°íve se budeme v¥novat rozklad·m, na které vzneseme je²t¥ jeden poºadavek totiº aby pouºité jazyky byly komutativní.
2.2
Komutativní jazyky
Komutativní jazyky nad zobrazení
Ψ
k -prvkovou
A
abecedou
p°irozen¥ ztotoºnit s podmnoºinami
s celo£íselnými sou°adnicemi) v
Nk .
lze prost°ednictvím Parikhova
m°íºových bod·
(to jsou body
To, zda daná podmnoºina m°íºových bod·
odpovídá jazyku, který je uzav°ený, lze pak pom¥rn¥ snadno ov¥°ovat díky tomu, ºe pro libovolná dv¥ slova
u, v
platí
Ψ(uv) = Ψ(u) + Ψ(v).
Zam¥°me se nejd°íve na p°ípad, kdy máme separovat dv¥ slova
w1 , w2 .
Pokud
mají tato slova lineárn¥ závislé Parikhovy obrazy, pak je pomocí uzav°ených komutativních jazyk· jist¥ separovat nelze (skute£n¥, existují-li ºe
k · Ψ(w1 ) = l · Ψ(w2 ),
pak m°íºový bod
k, l ∈ N
k · Ψ(w1 ) = l · Ψ(w2 )
taková,
musí náleºet
ob¥ma jazyk·m). Jak ukazuje následující tvrzení, v opa£ném p°ípad¥ lze naopak dv¥ slova separovat jednodu²e.
Tvrzení 2.4.
A´ mají slova
w1 , w2
nad abecedou
obrazy. Pak existuje uzav°ený rozklad takový, ºe jazyky
D·kaz:
w2
L1 , L2
L1 , L2
A
lineárn¥ nezávislé Parikhovy
mnoºiny
A+
separující slova
w1 , w2
jsou komutativní.
Postupujme po vzoru P°íkladu 1(ii). Jelikoº Parikhovy obrazy slov
jsou lineárn¥ nezávislé, existuje
a∈A
w1 ,
takové, ºe
|w1 |a |w2 |a 6= . |w1 | |w2 | Bez újmy na obecnosti p°edpokládejme, ºe
L1 = Jazyky
L1 , L2
w∈A ≤t |w| + |w|a
|w1 |a |w1 |
a
=t<
|w2 |a a poloºme |w2 |
L2 = A + \ L1 .
jsou z°ejm¥ komutativní, tvo°í rozklad
A+
a separují slova
w1 ,
w2 . Navíc jsou oba uzav°ené. Skute£n¥, pro kaºdá dv¥ slova u, v ∈ L1 je |u|a ≤ t·|u| a
|v|a ≤ t · |v|,
a tedy i
|uv|a = |u|a + |v|a ≤ t · (|u| + |v|) = t · |uv|, 8
L2
|w|a
w2
|w|a = t · |w| w1
L1 |w|
Obrázek 2.1: Rozklad separující slova s lineárn¥ nezávislými Parikhovy obrazy
takºe
uv ∈ L1
|v|a > t · |v|,
a jazyk
L1
je uzav°ený. Podobn¥ pro
takºe
u, v ∈ L2
je
|u|a > t · |u|
a
|uv|a = |u|a + |v|a > t · (|u| + |v|) = t · |uv| a
L2
je rovn¥º uzav°ený.
Pro úplnost je²t¥ ukaºme, ºe vý²e uvedená konstrukce uzav°eného rozkladu na komutativní jazyky je (alespo¬ v p°ípad¥ dvouprvkové abecedy) principiáln¥ jediná.
Tvrzení 2.5.
A´
{L1 , L2 }
je uzav°ený rozklad mnoºiny
{0, 1}+
na dva komu-
t ∈ [0, 1] takové, ºe jeden z jazyk· obsahuje slova w ∈ {0, 1} | |w|1 < t · |w| , druhý obsahuje slova w ∈ {0, 1}+ | |w|1 > t · |w| a jeden z nich navíc obsahuje i slova w ∈ {0, 1}+ | |w|1 = t · |w| .
tativní jazyky. Pak existuje
+
D·kaz: Uvaºme libovolný uzav°ený rozklad
tivní jazyky a ozna£me tvo°í
M1
a
M2
M1 = Ψ(L1 ) a M2 = Ψ(L2 ). Protoºe Ψ(uv) = Ψ(u)+Ψ(v),
rozklad mnoºiny
sloºkách. Bez újmy na obecnosti a´
a, b ∈ N
{L1 , L2 } mnoºiny {0, 1}+ na komuta-
ne ob¥ nulová je i
N2 \ {[0, 0]}
[1, 0] ∈ M1 .
uzav°ený vzhledem ke s£ítání po
Pokud
[0, 1] ∈ M1 ,
pak pro libovolná
[a, b] = a · [1, 0] + b · [0, 1] ∈ M1 , takºe
M2 = ∅
a v d·sledku toho i
L2 = ∅,
coº nep°ipou²tíme. Proto
Díky uzav°enosti obou p·vodních jazyk· je
a ∈ N.
[a, 0] ∈ M1
Pro spor nyní p°edpokládejme, ºe poºadované
body
x = [x0 , x1 ] ∈ M1
takové, ºe
x1 x0 +x1
≥
t
a
[0, 1] ∈ M2 .
[0, a] ∈ M2
pro kaºdé
neexistuje, tedy ºe existují
a y = [y0 , y1 ] ∈ M2 se v²emi sou°adnicemi nenulovými y1 y1 x neboli ºe 1 ≥ . y0 +y1 x0 y0
9
|w|1
?
x1 y1 y0 x0
|w|0
Obrázek 2.2: Principiální jednozna£nost uzav°eného rozkladu na komutativní jazyky
Jelikoº
[y0 , y1 ] ∈ M2 ,
je i
p°edpokladu ov²em máme
x0 · [y0 , y1 ] = [x0 y0 , x0 y1 ] ∈ M2 .
x1 y0 ≥ x0 y1 ,
coº spolu s
[0, 1] ∈ M2
Roznásobením
dává
y0 · [x0 , x1 ] = [x0 y0 , x1 y0 ] = x0 · [y0 , y1 ] + (x1 y0 − x0 y1 ) · [0, 1] ∈ M2 . | {z } | {z } | {z } |{z} ∈M1
≥0
∈M2
∈M2
To je kýºený spor.
Poznámka 2.6. Poznamenejme, ºe podobný výsledek platí i pro rozklad mnoºiny {0, 1}+
na
k >2
uzav°ených jazyk·. P°esn¥ji tvrdíme, ºe pro libovolný takový
rozklad musí Parikh·v obraz kaºdého díl£ího jazyka
Li sestávat z m°íºových bod·
uvnit° jistého úhlu s vrcholem v po£átku soustavy sou°adnic, p°ípadn¥ dopln¥ných o m°íºové body na jednom £i obou svých ramenech (bez vrcholu samotného). Skute£n¥ kdyby existovaly m°íºové body o nenulových sou°adnicích
[x0 , x1 ] x1 x0
≤
y1 y0
a
Z = [z0 , z1 ]
≤
náleºející
Ψ(Li )
a
Y = [y0 , y1 ]
náleºející
Ψ(Lj )
X =
takové, ºe
z1 , pak by bod z0
(y0 z1 − y1 z0 ) · [x0 , x1 ] + (x0 y1 − x1 y0 ) · [z0 , z1 ] = (x0 z1 − x1 z0 ) · [y0 , y1 ] | {z } | {z } | {z } | {z } | {z } | {z } ≥0
≥0
∈Ψ(L1 )
musel leºet zárove¬ v
Ψ(L1 )
a
∈Ψ(L1 )
nemusíme ur£ovat. Sta£í si uv¥domit, ºe vektory
Y
leºí mezi
X
a
Z,
∈Ψ(L2 )
Ψ(L2 ).
Tajuplné hodnoty, jimiº se násobí sou°adnice vektor·
protoºe
≥0
X, Y , Z
X, Y
a
Z,
v zásad¥ ani
jsou lineárn¥ závislé, a
bude v jejich netriviální lineární kombinaci, která
dá nulový výsledek, odli²né znaménko práv¥ u n¥j. Podle domn¥nky vy°£ené v [2] by se p°i zachování p°edpokladu lineární nezávislosti Parikhových obraz· kaºdé dvojice slov m¥lo dát separovat uzav°enými komutativními jazyky i více slov neº dv¥. Tak tomu skute£n¥ je. K d·kazu budeme pot°ebovat následující ryze mohutnostní lemma.
10
Lemma 2.7.
Ozna£me
X ∈ Nk+
existuje bod
Pro kaºdé
D·kaz:
U
sjednocení
leºící v
i ∈ N+
n
vlastních podprostor· prostoru
Rk .
Pak
Rk \ U .
uvaºme m°íºový bod
Xi
o sou°adnicích
Xi = [i0 , i1 , . . . , ik−1 ]. Jelikoº kaºdých matice typu
k
takových bod· je lineárn¥ nezávislých (zapí²eme-li je do °ádk·
k × k,
získáme tzv. Vandermondovu matici, která má nenulový de-
terminant), m·ºe kaºdý z
k−1
n vlastních podprostor· prostoru Rk
obsahovat nejvý²e
z nich.
Tím pádem pro nejvý²e
j
jist¥ existuje index
n(k − 1)
takový, ºe
index·
i
leºí bod
Xi
ve sjednocení
U,
takºe
Xj ∈ / U.
A nyní uº samotná v¥ta.
V¥ta 2.8.
A´
n ∈ N
a
w1 , . . . , w n
taková, ºe pro kaºdou dvojici index· slov
+
A
wi
a
wj
{0, 1}+
i, j ∈ {1, . . . , n}, i 6= j , jsou Parikhovy obrazy
lineárn¥ nezávislé. Pak existuje uzav°ený rozklad
w1 , . . . , w n
separující slova
takový, ºe jazyky
Nejd°íve ukáºeme, ºe kaºdé z
D·kaz:
k
L1 , . . . , L n
{Li }ni=1
do posloupnosti nul a jedni£ek tak, aby ºádná dv¥ ze slov
N2 ).
k = 2,
c: A →
c(w1 ), . . . , c(wn )
Tím tvrzení p°evedeme na p°í-
kde jeho d·kaz snadno dokon£íme.
Kaºdé z písmen
ai , i = 1, . . . , k ,
jednou jedni£kou následovanou stanty. Pro slovo
w ∈ A+
Parikh·v obraz slova
0
mnoºiny
jsou komutativní.
písmen lze zakódovat funkcí
nem¥la lineárn¥ závislé Parikhovy obrazy (v pad
A = {a1 , . . . , ak }
jsou slova nad abecedou
Ψ (c(w)) =
i=1
xi − 1
nulami, kde
s Parikhovým obrazem
c(w)
k X
zakódujeme posloupností délky
roven
|w|ai (xi − 1),
k X i=1
! |w|ai
=
xi
xi
tvo°enou
jsou zatím neur£ené kon-
Ψ(w) = (|w|a1 , . . . , |w|ak ) k X i=1
je tak
! |w|ai (xi − 1), |w| .
Zd·razn¥me, ºe zde uvaºujeme dv¥ r·zná Parikhova zobrazení:
Ψ : w ∈ A+ 7→ (|w|a1 , . . . , |w|ak ) ∈ Nk a
Ψ0 : c(w) ∈ {0, 1}+ 7→ (|c(w)|0 , |c(w)|1 ) ∈ N2 . Slova
|u|1 kdyº |u|
u, v ∈ {0, 1}+
mají lineárn¥ nezávislé Parikhovy obrazy práv¥ tehdy,
1 6= |v| . Konstanty x1 , . . . , xk ∈ N proto pot°ebujeme zvolit tak, aby pro |v| 0 0 kaºdou dvojici index· j, j ∈ {1, . . . , n}, j 6= j , platilo
|c(wj )|1 |c(wj 0 )|1 6= |c(wj )| |c(wj 0 )|
neboli
Pk
|wj |
i=1
11
|wj |ai xi
6= Pk
|wj 0 |
i=1
|wj 0 |ai xi
.
Zvolme
j , j 0 pevn¥ a zkoumejme, kdy se naopak ob¥ strany rovnají. Roznásobením
získáme
k X i=1
Závorka, kterou se násobí
xi · (|wj 0 |ai |wj | − |wj |ai |wj 0 |) = 0. xi ,
je nulová práv¥ tehdy, kdyº je
|wj 0 |ai |wj |ai = . |wj 0 | |wj | Jelikoº slova
wj , wj 0
nemají z p°edpokladu lineárn¥ závislé Parikhovy obrazy, je
hodnota alespo¬ jedné závorky v p·vodní rovnici nenulová a tato rovnice tak popisuje nejvý²e
(k − 1)-dimenzionální
podprostor v
Rk .
1 n(n−1) dvojic r·zných index· j, j 0 ∈ {1, . . . , n} 2 k dostaneme jiné nevhodné podprostory v R . Díky Lemmatu 2.7 t¥chto kone£n¥ Obdobnou úvahou pro v²ech
mnoho vlastních podprostor· nepokrývá v²echny m°íºové body vektor
Nk+ , takºe existuje
(x1 , . . . , xk ) s kladnými celými sou°adnicemi, který ur£uje kódování takové,
ºe Parikhovy obrazy kód· kaºdých dvou zadaných slov
w1 , . . . , w n
jsou lineárn¥
nezávislé. Dokon£ení d·kazu je nyní nasnad¥. Pro v¥t²í p°ehlednost ozna£me
+
vi ∈ {0, 1}
c(wi ) =
. Bez újmy na obecnosti p°edpokládejme, ºe
|v1 |0 |v2 |0 |vn |0 < < ··· < |v1 |1 |v2 |1 |vn |1 (jmenovatele jsou z°ejm¥ nenulové) a nalezn¥me konstanty
Pro
t1 , . . . , tn−1
|v1 |0 |v2 |0 |vn |0 < t1 < < t2 < · · · < tn−1 < . |v1 |1 |v2 |1 |vn |1 n o |v|0 i = 1, . . . , n nyní poloºme Li = v ∈ {0, 1}+ ti−1 ≤ |v| < t , i 1
t0 = 0
a
tn = ∞.
|v|0 = tn−1 · |v|1
|v|0 vn
v3
|v|0 = t2 · |v|1 |v|0 = t1 · |v|1
v2 v1
|v|1 Obrázek 2.3: Rozklad separující kódová slova
12
takové, ºe
kde klademe
Podobn¥ jako v d·kazu Tvrzení 2.4 ukáºeme, ºe
{0, 1}+
rozklad
n
{(Ψ0 )−1 (Li )}i=1
na komutativní jazyky separující slova
to jazyk· v kódování
c
v1 , . . . , vn . A+
pak tvo°í kýºený uzav°ený rozklad
je uzav°ený Vzory t¥ch-
separující slova
w1 , . . . , w n .
Jak jsme vid¥li v P°íkladech 1 (iii) a (iv), ne v²echny uzav°ené rozklady sestávají z komutativních jazyk·. A£koliv je zkoumání rozklad· v obecném p°ípad¥ pochopiteln¥ obtíºn¥j²í, vý²e p°edstavenou geometrickou ideu se nám poda°í za cenu jistých komplikací roz²í°it i pro n¥.
2.3
Geometrický p°ístup
V této £ásti podáme geometrický d·kaz V¥ty 2.3. Op¥t za£neme p°ípadem, kdy máme separovat jen dv¥ slova (d·kaz je p°evzatý z £lánku [1]).
Tvrzení 2.9.
tují. Pak existuje uzav°ený rozklad mnoºiny
Postupujme indukcí podle sou£tu
D·kaz:
|u| + |v| = 2
Pro
A
nekomu-
pro n¥jaká r·zná písmena
a, b ∈ A.
P°edpokládejme, ºe neprázdná slova
musí být
u=a
a
A
+
u, v
nad abecedou
separující
|u| + |v| > 2.
v=b
Pokud existuje
a
v.
|u| + |v|.
Pak sta£í (stejn¥ jako v P°íkladech 1 (i)) za rozklad vzít Nyní a´
u
a∈A
+
+
|u|a |u|
6=
+
{a , A \ a }.
takové, ºe
|v|a , nalezneme |v|
uzav°ený rozklad stejn¥ jako v Tvrzení 2.4. Dále proto p°edpokládejme, ºe pro v²echna
a∈A
Uvaºme slova
u
a
v
je
|u|a |u|
=
|v|a . |v|
a ∈ A takové, ºe
|u|a |u|
|v|a |v|
=
mocninou téhoº písmene
a
= t > 0. Jist¥ t < 1, protoºe jinak by byla a komutovala by. Poloºme
L< = w ∈ A+ |w|a < t · |w| , L= = w ∈ A+ |w|a = t · |w| , L> = w ∈ A+ |w|a > t · |w| . Trojice
{L< , L= , L> }
tvo°í uzav°ený rozklad
najdeme-li te¤ uzav°ený rozklad
{M1 , M2 }
budeme hotovi, nebo´ za uzav°ený rozklad
A+
jazyka
+
A
a
=
L
u, v ∈ L= .
Tvrdíme, ºe
separující slova
u
a
v,
bude sta£it vzít dvojici
{L< ∪ M1 , M2 ∪ L> } . e dvojice
{L< ∪ M1 , M2 ∪ L> }
tvo°í rozklad separující
domme si tedy je²t¥, ºe oba jazyky jsou uzav°ené. Pro
M1 i xy ∈ M1 .
Pro
x ∈ L<
a
y ∈ L< ∪ M1
je
u
a
x, y ∈ M1
|xy|a = |x|a + |y|a < t · |x| + t · |y| = t · |xy|, 13
v
je z°ejmé, uv¥-
je z uzav°enosti
takºe
xy ∈ L1
a obdobn¥
analogicky.
yx ∈ L1 .
Uzav°enost jazyka
1 m k
· |v|a
t < 1,
jsou násobky
m.
je
m ≥
L= .
Ozna£me
t =
Jelikoº
|u| + |v|,
mnoºiny
B
Uvaºme proto novou abecedu
m-tic písmen abecedy A a p°edpokládejme, ºe slova u, v vyjád°ena po °ad¥ slovy
se ukáºe zcela
k , kde k, m ∈ N+ jsou m 2. V²imn¥me si, ºe |u| = k1 m · |u|a a |v| =
Zbývá najít onen rozklad jazyka nesoud¥lná. Jelikoº
M2 ∪ L>
v²ech uspo°ádaných
jsou v této nové abeced¥
r, s ∈ B + .
k (|u|+|v|) m
u a v nekomutují, nekomutují ani r a s. Zárove¬ |r|+|s| =
takºe z induk£ního p°edpokladu existuje uzav°ený rozklad
B+.
abecedou
A,
Nahlédneme-li te¤ na jazyky
sta£í poloºit
M1 = N1 ∩ L
=
a
N1 , N2
<
{N1 , N2 }
znovu jako na jazyky nad
M2 = N2 ∩ L=
a jsme hotovi.
D·kaz p°edchozího tvrzení projde beze zm¥ny, budeme-li namísto mnoºiny
A+ = w ∈ A+ (∀i = 1, . . . , k) : 0 · |w| ≤ |w|ai ≤ 1 · |w| obecn¥ji rozkládat mnoºinu
L = w ∈ A+ (∀i = 1, . . . , k) : ti |w| ≤ |w|ai ≤ ui |w| , kde
ti , ui , i = 1, . . . , k ,
0 ≤ ti ≤ ui ≤ 1.
jsou konstanty spl¬ující pro kaºdé
i = 1, . . . , k
Libovolnou neostrou nerovnost v popisu jazyka
L
vztahy
navíc m·ºeme
nahradit ostrou nerovností. D·kaz p°edchozího tvrzení zárove¬ skýtal algoritmus, jak poºadovaný uzav°ený rozklad nalézt. P°edvedeme ho na p°íkladu.
P°íklad. tak pro
b,
Uvaºme
A = {a, b}, u = aabb, v = abba.
Pak
|u|a |u|
=
1 2
=
|v|a a stejn¥ |v|
takºe si nevysta£íme s Tvrzením 2.4. V souladu s d·kazem p°ede²lého
tvrzení poloºme
1 L = w ∈ A |w|a < · |w| , 2 1 = + L = w ∈ A |w|a = · |w| , 2 1 > + L = w ∈ A |w|a > · |w| . 2
<
Pro
a∈A
jsme jiº spo£etli
k m
=
+
1 . Uvaºme tedy abecedu 2
B = {p = aa, q = ab, r = ba, s = bb} dvojic písmen z
A.
Pak
u = ps
a
v = qr,
£ímº jsme sníºili hodnotu
navíc m·ºeme pouºít Tvrzení 2.4 a nalézt uzav°ený rozklad v podob¥
N1 = w ∈ B + |w|q = 0
a
14
|u| + |v|.
{N1 , N2 }
N2 = w ∈ B + |w|q > 0 .
jazyka
Te¤
B+
Proniknutím s
L=
a následným sjednocením s jazykem
M1 = L< ∪ (L= ∩ N1 ) Jazyk
L<
tak získáme jazyky
M2 = A+ \ M1
a
M1 pro p°edstavu sestává ze slov w, pro která platí |w|a < |w|b , a ze slov,
která sou£asn¥ spl¬ují indexu. Jazyk
M2
|w|a = |w|b
a neobsahují podslovo
ab
za£ínající na lichém
je pak tvo°en v²emi ostatními slovy.
Nyní uº jsme p°ipraveni dokázat V¥tu 2.3 v její plné síle. D·kaz probíhá velmi analogicky k d·kazu Tvrzení 2.9. D·kaz: (V¥ta 2.3, geometrický zp·sob) Op¥t postupujme indukcí, tentokrát dvo-
jitou: jednak podle po£tu
· · · + |wn | Pro
jejich délek.
n=2
kaºdé slovo
n slov, která máme separovat, dále podle sou£tu |w1 | +
sta£í pouºít p°edchozí tvrzení. Pro
wi , i = 1, . . . , n
|w1 | + · · · + |wn | = n
rovnat jinému písmenu
ai
abecedy
A
se musí
a za uzav°ený
rozklad poslouºí
( + + a+ 1 , . . . , an−1 , A \ Dále a´
n>2
a
|w1 | + · · · + |wn | > n.
Pokud existuje
a∈A
a dvojice index·
|wj |a , uvaºme jazyky |wj |
L≤ = w ∈ A+ | |w|a ≤ t · |w| které tvo°í uzav°ený rozklad
A+ .
a
n−1 [
) a+ i
.
i=1
i, j ∈ {1, . . . , n}
taková, ºe
Kaºdý z nich obsahuje ost°e mén¥ neº
jichº slou£ením získáme poºadovaný uzav°ený rozklad
t ∈ (0, 1).
+
A
L≤
potaºmo
n
slov,
L> ,
a∈A
platí, ºe pro v²echna
je-
.
|wi |a |wi | |wi |a A, pro které je spole£ná hodnota v²ech zlomk· |wi |
Pokud pro kaºdé pevné
a∈
=t<
L> = w ∈ A+ | |w|a > t · |w| ,
takºe z induk£ního p°edpokladu existují uzav°ené rozklady
|wj |a , uvaºme takové |wj |
|wi |a |wi |
i, j ∈ {1, . . . , n}
je
= =
Op¥t poloºme
L< = w ∈ A+ |w|a < t · |w| , L= = w ∈ A+ |w|a = t · |w| , L> = w ∈ A+ |w|a > t · |w| . Trojice
{L< , L= , L> } tvo°í uzav°ený rozklad A+ . Najdeme-li uzav°ený rozklad
{M1 , . . . , Mn }
jazyka
uzav°ený rozklad
A+
L=
separující slova
budeme moci vzít
w1 , . . . , w n ,
budeme hotovi, nebo´ za
n-tici
{L< ∪ M1 , M2 , . . . , Mn−1 , Mn ∪ L> } . 15
Op¥t ozna£me
i = 1, . . . , n
je
uspo°ádaných v abeced¥
B
t =
|wi | =
k , kde k, m ∈ N+ jsou nesoud¥lná a m ≥ 2. Pro kaºdé m 1 m · |wi |a násobek m, takºe uváºíme-li abecedu B v²ech k
m-tic písmen abecedy A, lze pro kaºdé i = 1, . . . , n slovo wi vyjád°it xi .
n¥jakým slovem
Jelikoº pro pádem z
i 6= j
slova
wi
n X i=1
a
wj
nekomutují, nekomutují ani slova
n
xi
a
xj .
Tím
n
X k X |xi | = |wi | < |wi | m i=1 i=1
a z induk£ního p°edpokladu vyplývá, ºe existuje uzav°ený rozklad
{Ni }ni=1 mnoºiny
B + . Za uzav°ený rozklad {Mi }ni=1 mnoºiny L= pak pro kaºdé i = 1, . . . , n vezmeme
Mi = Ni ∩ L=
a jsme s d·kazem u konce.
Klí£ovou roli v celém dosavadním pr·b¥hu hrálo zobrazení
w
které slovu
p°i°adilo hodnotu
|w|a , kde |w|
a
f : A+ → [0, 1],
bylo n¥jaké pevné písmeno abecedy
A. Toto zobrazení respektuje konkatenaci v následujícím smyslu: Platí-li pro slova u, v ∈ A+ vztah f (u), f (v) ≥ t pro n¥jakou reálnou konstantu t, pak je i f (uv) ≥ t,
p°i£emº rovnost ve t°etí nerovnosti nastane jen tehdy, kdyº nastanou sou£asn¥ rovnosti v té první a druhé. Byla to práv¥ tato vlastnost, díky níº jsme byli schopni snadno konstruovat uzav°ené rozklady. Takto popsané zobrazení
f
v²ak není dostate£n¥ jemné n¥kterým nekomu-
tujícím slov·m p°i°azuje stejnou hodnotu (p°i°azuje totiº stejnou hodnotu práv¥ t¥m slov·m, která mají týº Parikh·v obraz). Separace práv¥ takových slov pak zp·sobovala komplikace, které jsme v d·kazu V¥ty 2.3 museli obcházet pom¥rn¥ nep°íjemným induktivním argumentem. V následujícím zásadní m¥rou vyuºijeme toho, ºe existuje funkce, která respektuje konkatenaci, a p°itom rozli²í libovolná dv¥ nekomutující slova.
2.4
Binární p°ístup
V této £ásti podáme jiný d·kaz V¥ty 2.3. Nejd°íve si uv¥domme, ºe se m·ºeme bez újmy na obecnosti omezit na slova nad dvouprvkovou abecedou s písmeny 0 a 1, kterou budeme nadále zna£it
B = {0, 1}. B+,
Pro
k>2
které pro kaºdé
a
A = {a1 , . . . , ak }
i = 1, . . . , k
totiº sta£í uvaºovat zobrazení
p°i°adí písmenu
jedni£ku práv¥ na i-té pozici. Homomor smus
ϕ,
dukován, je pak prostý a nekomutujícím slov·m tující slova
ai
slovo
bi
délky
k
f: A →
obsahující
který je tímto zobrazením
f
in-
u, v ∈ A+ p°i°azuje op¥t nekomu-
ϕ(u), ϕ(v) ∈ B + . Pokud tedy najdeme uzav°ený rozklad B + separující
ϕ(w1 ), . . . , ϕ(wk ),
získáme tím i uzav°ený rozklad
16
A+
separující
w1 , . . . , w k .
Kaºdé slovo nad abecedou
B
lze vnímat jako £íslo zapsané ve dvojkové sou-
stav¥, jehoº zápis neza£íná nutn¥ jedni£kou. Precizn¥ji:
De nice.
A´
rozumíme £íslo
n ∈ N+
a
w = x1 x2 . . . xn ∈ B + . Binární hodnotou b(w) =
n X i=1
slova
w
xi · 2n−i .
Takto de novaná binární hodnota má z°ejm¥ následující vlastnosti.
Pozorování 2.10. (i)
u, v ∈ B + .
A´
Pak
b(uv) = b(u 00 . . . 0}) + b(v) = b(u) · 2|v| + b(v), | {z |v|×
(ii)
u=v
práv¥ tehdy, kdyº sou£asn¥
|u| = |v|
a
b(u) = b(v).
Co je v²ak d·leºit¥j²í, lze pomocí ní charakterizovat, kdy dv¥ slova komutují.
Tvrzení 2.11.
A´
u, v ∈ B + .
Pak
u
a
v
komutují práv¥ tehdy, kdyº
b(u) b(v) = . 2|u| − 1 2|v| − 1 D·kaz:
Slova
u
a
v
komutují práv¥ tehdy, kdyº
uv = vu.
nastane toto díky Pozorování 2.10(i) a (ii) práv¥ tehdy, kdyº
b(uv) = b(vu) = b(v) · 2|u| + b(u),
Poznámka 2.12.
neboli kdyº
b(u) 2|u| −1
=
Jelikoº
|uv| = |vu|,
b(u) · 2|v| + b(v) =
b(v) . 2|v| −1
b(u) lze také chápat jako £íslo, jehoº zápis ve dvoj2|u| −1 b(u) kové soustav¥ je periodický tvaru 0,uuu . . . (nap°íklad pro u = 110 je |u| = 2 −1 4 = (0,110)2 ). Z tohoto náhledu je p°edchozí tvrzení rovn¥º patrné pro slova u, 7
v
totiº nastane
Hodnotu
0,u = 0,v
práv¥ tehdy, kdyº jsou
u
a
v
mocninou téhoº slova, coº
je díky Lemmatu 1.2 ekvivalentní tomu, ºe komutují. Jsme p°ipraveni seznámit se s jiným d·kazem V¥ty 2.3 v p°ípad¥ abecedou D·kaz:
B,
slov nad
který je uveden v [2].
(V¥ta 2.3, binární zp·sob) Jelikoº z p°edpokladu slova
pro ºádnou dvojici index· pro
n
i = 1, . . . , n
i, j ∈ {1, . . . , n}, i 6= j ,
wi , wj
nekomutují
jsou hodnoty zlomk·
navzájem r·zné. Bez újmy na obecnosti p°edpokládejme
b(w2 ) b(wn ) b(w1 ) < |w2 | < · · · < |wn | −1 2 −1 2 −1
2|w1 | a nalezn¥me konstanty
t1 , . . . , tn−1 ∈ (0, 1)
takové, ºe
b(w1 ) b(w2 ) b(wn ) < t1 < |w2 | < t2 < · · · < tn−1 < |wn | . −1 2 −1 2 −1
2|w1 |
17
b(wi ) 2|wi | −1
Pro kaºdé
i = 1, . . . , n
poloºme
Li =
b(w) < ti , w ∈ B ti−1 ≤ |w| 2 −1 +
t0 = 0
a tn = 2. n Systém {Li }i=1 tvo°í rozklad
kde klademe
B+
separující slova
w1 , . . . , wn . Zbývá ukázat, ºe
pouºité jazyky jsou uzav°ené.
P°edpokládejme proto, ºe pro slova
ti−1 ≤
u, v ∈ B +
platí
b(u) b(v) ≤ |v| < ti . −1 2 −1
2|u|
Pak je ov²em
b(uv) = b(u) · 2|v| + b(v) ≥ ti−1 · (2|u| − 1) · 2|v| + ti−1 · (2|v| − 1) = ti−1 · (2|uv| − 1) a zcela analogicky odvodíme i
b(uv) = b(u) · 2|v| + b(v) < ti · (2|u| − 1) · 2|v| + ti · (2|v| − 1) = ti · (2|uv| − 1), takºe
ti−1 ≤
b(uv) 2|uv| −1
< ti
rovn¥º. Jsme hotovi.
Na záv¥r op¥t na p°íkladu oz°ejmíme, jak lze poºadovaný rozklad nalézt v praxi. Postup demonstrujeme na stejné dvojici slov jako v p°íkladu u první metody. Ukazuje se, ºe nalezený rozklad je jiný.
P°íklad. Pak
Uvaºme
B = {0, 1}, u = 1001, v = 1100.
b(u) = 8 + 1 = 9, b(v) = 8 + 4 = 12
a
|u| = |v| = 4,
takºe
b(u) 3 4 b(v) = < = |v| . −1 5 5 2 −1
2|u| M·ºeme volit nap°íklad
t1 =
2 . Odpovídající jazyky pak vypadají následovn¥: 3
b(w) 2 L1 = w ∈ B |w| < = {0; 00, 01; 000, 001, 010, 011, 100; 0000, . . . } , 2 −1 3 2 + b(w) L2 = w ∈ B |w| ≥ = {1; 10, 11; 101, 110, 111; 1010, 1011, . . . } . 2 −1 3
+
18
Záv¥r Ukázali jsme, ºe podmínka na lineární nezávislost Parikhových obraz· libovolných dvou slov, která je v p°ípad¥ separace
n slov pomocí komutativních jazyk· z°ejm¥
nutná, je i posta£ující, £ímº jsme potvrdili domn¥nku z [2]. P°edvedli jsme také dva r·zné zp·soby jak zkonstruovat uzav°ený rozklad separující daná dv¥ nekomutující slova jeden inspirovaný p°ístupem v £lánku [1], druhý p°evzatý z £lánku [2]. Pokud bychom cht¥li vzniklé jazyky kvalitativn¥ porovnat, museli bychom se hloub¥ji v¥novat teorii formálních gramatik a automat·, coº je mimo rozsah této práce. A£ bez pot°ebných de nic, nazna£me alespo¬ výsledek. Ukazuje se, ºe konstrukce popsaná jako druhá vºdy vytvá°í regulární jazyky, coº jsou jazyky, které jsou ve smyslu Chomského hierarchie t¥mi nejspeciáln¥j²ími jazyky v·bec (mimo jiné jsou to jazyky rozpoznatelné kone£ným automatem). Jazyky vzniklé prvním p°ístupem oproti tomu nejenºe obecn¥ nemusejí být regulární, ale dokonce nemusejí být ani bezkontextové (a£koliv kontextové uº jsou vºdy). D·kaz t¥chto tvrzení lze nalézt v [2]. Pot°ebné pojmy jsou objasn¥ny v [4].
19
Seznam pouºité literatury [1] Brzozowski, J. A., Grant, E., Shallit, J., Closures in Formal Languages and Kuratowski's Theorem, International Journal of Foundations of
Computer Science,
22(2): 301321 (2011)
[2] Holub, ., Kortelainen, J., On Partitions Separating Words, International Journal of Algebra and Computation,
21(8): 13051316 (2011)
[3] Lothaire, M., Combinatorics on words, 2. vydání, Cambridge University Press, 1997, ISBN 0-521-59924-5 [4] Rozenberg, G., Salomaa, A., Handbook of Formal Languages: Volume I. Word, Language, Grammar, 1. vydání, Springer, 1997, ISBN 3-540-60420-4
20
