Sanojen kombinatoriikka

Sanojen kombinatoriikka on 1900-luvun lopulla kehittynyt matematiikan ja teoreettisen tietojenkäsittelytieteen haara, jossa tutkitaan sanoja symbolijonoina ilman semanttista merkitystä. Sovelluksia löytyy esimerkiksi molekyylibiologiasta, jossa DNA:ta voidaan mallintaa sanoina nelikirjaimisessa aakkostossa A,C,G, T.

Symboliaakkosto merkitään usein $\Sigma$ (kreikkalaisen aakkoston iso sigma-kirjain). Tällöin DNA:n kohdalla $\Sigma =\{A,C,G,T\}$ ja bittien kohdalla $\Sigma =\{0,1\}$. Yleensä vaaditaan, että symboliaakkoston on oltava äärellisen kokoinen, ja usein käytetty esimerkki edellisten lisäksi on $\Sigma =\{a,b,c\}$, jolloin kyseessä on siis 3-kirjaiminen symboliaakkosto.

Symboliaakkostoon liittyvä sana on mikä tahansa äärellisen pituinen merkkijono, jonka merkit kuuluvat annettuun symboliaakkostoon, ja sanan pituus on sen merkkien lukumäärä. Esimerkiksi $\Sigma =\{a,b,c\}$-aakkoston kohdalla $bbacb$ on eräs 5-pituinen sana ja $acccbccaba$ on eräs 10-pituinen sana. Sanoja merkitään usein "sanamuuttujilla" kuten $w,u,v,x$ tai $y$, jolloin $\vert w\vert$ merkitsee $w$-sanan pituutta. Esimerkiksi jos $w=acba$, $\vert w\vert =4$.

Tietyn symboliaakkoston $\Sigma$ määräämää sanojen joukkoa merkitään $\Sigma ^{*}$, ja siihen kuuluu lisäksi tyhjä sana, jossa ei ole yhtään symbolia (Se on siis 0-pituinen.), ja jota merkitään usein $\epsilon$ (kreikkalaisen aakkoston pieni epsilon-kirjain). Selvästi $\Sigma ^{*}$-joukon eri sanoja on (numeroituvasti) ääretön määrä: 0-pituinen tyhjä sana $\epsilon$, 1-pituiset, 2-pituiset, jne.

Äärellisen pituisten sanojen lisäksi toisinaan tarkastellaan äärettömän pituisia sanoja, joiden kohdalla symbolijono jatkuu äärettömän pitkälle oikealle. Näin on esimerkiksi, kun $w=abcabcabcabc...$, missä $abc$-"jakso" jatkuu oikealle äärettömän monta kertaa, mutta tietenkään kaikkien äärettömän pitkien sanojen rakenteen ei tarvitse olla näin säännöllinen.

Sanojen kohdalla niiden välinen peruslaskutoimitus on tulo eli katenaatio, joka yksinkertaisesti tarkoittaa kerrottavien sanojen symbolijonojen asettamista peräkkäin niin, että näin muodostuu uusi sana. Esimerkiksi jos $w=abbca$, $u=bbbcaa$ ja $.$ merkitsee tuloa, $w.u=abbca.bbbcaa=abbcabbbcaa$ tai $u.\epsilon =bbbcaa.\epsilon =bbbcaa$. Selvästi tämä tulo on epäkommutatiivinen (Sillä yleensä $w.u\neq u.w$.) ja assosiatiivinen (Sillä $(w.u).v=w.(u.v)$ suoraan symbolien peräkkäin asettamisesta johtuen, koska $w,u$ ja $v$ ovat molemmilla puolilla samassa vasemmalta-oikealle-järjestyksessä.).

Assosiatiivisuudesta johtuen sulkumerkit ovat tuloissa tarpeettomia, eli voidaan merkitä $(w.u).v=w.(u.v)=w.u.v$ ja yleisemminkin esimerkiksi $w.x.u.y.v$. Usein "tulopisteetkin" jätetään merkitsemättä, jolloin äskeinen lyhenee muotoon $wxuyv$. Tällä tulo-operaatiolla varustettu $\Sigma ^{*}$-joukko on vapaa monoidi, mistä seuraa, että sanojen tutkimus on yhteydessä myös algebraan.

Tärkeä tulon erikoistapaus on sanan potenssi, joka tarkoittaa sanan kertomista itsellään eksponentin osoittaman määrän, eli siis $w^{\mathbf {n} }=www...w$, missä $w$-sanoja on peräkkäin n kappaletta. Esimerkiksi jos $w=accb$ ja $n=4$, niin $w^{\mathbf {n} }=wwww=accbaccbaccbaccb$. Lisäksi määritellään luonnolliseen tapaan, että $w^{\mathbf {1} }=w$ ja $w^{\mathbf {0} }=\epsilon$.

Myös prefixin käsite on tärkeä. Sana $w$ on sanan $u$ prefix silloin, kun sanan $w$ kirjainjono muodostaa sanan $u$ kirjainjonon alkuosan, mikä merkitään $w\leq u$. Esimerkiksi $w=caba\leq cababcc=u$, ja lisäksi $\Sigma ^{*}$:n kaikilla sanoilla $w$ on tietenkin voimassa se, että $w\leq w$ ja $\epsilon \leq w$.

Sanojen kombinatoriikka tutkii mm. seuraavanlaisia kysymyksiä.

Esimerkki 1) Millaisten ehtojen vallitessa sanat kommutoivat, eli $w.u=u.w$.

On selvää, että sanat $w$ ja $u$ kommutoivat ainakin silloin, jos molemmat ovat saman sanan $v$ potensseja, eli $w=v^{\mathbf {n} }$ ja $u=v^{\mathbf {m} }$, jolloin $w.u=v^{\mathbf {(n+m)} }=v^{\mathbf {(m+n)} }=u.w$. Esimerkiksi jos $v=baca$ ja $w=v^{2}$ ja $u=v^{1}$, $w.u=bacabacabaca=u.w$. On melko helposti osoitettavissa, että tämä saman $v$-sanan potensseina oleminen on riittävyyden lisäksi myös välttämätön ehto sille, että sanat $w$ ja $u$ kommutoisivat, eli $w.u$ on sama sana kuin $u.w$.

Esimerkki 2) Onko mahdollista, että äärettömän pitkälle oikealle jatkuva sana ei sisällä "neliötä" eli samaa "jaksoa" kahta kertaa peräkkäin. Jos näin on, mikä on pienin symboliaakkoston koko, jolloin tämä on mahdollista.

On selvää, että ainakaan 2-kirjaimisessa symboliaakkostossa tämä ei ole mahdollista, sillä selvästi siinä pisimmät "neliötä" sisältämättömät sanat ovat $aba$ ja $bab$, mutta esimerkiksi jo $baba=(ba)(ba)$ eli siinä $ba$ on toistuvana "jaksona". Myös yllä esitetty oikealle ääretön sana sisältää "neliön", sillä siinä $abc$-"jakso" toistuu peräkkäin kahdesti. Esimerkiksi sana $cabcacbacabcacbcacba$ voi ensisilmäyksellä näyttää "neliöttömältä", mutta se silti sisältää $bcac$-"jakson" kahdesti peräkkäin, sillä $cabcacbacabcacbcacba=cabcacbaca(bcac)(bcac)ba$. Osoittautuu kuitenkin, että jo 3-kirjaimisessa aakkostossa on löydettävissä tällaisia oikealle äärettömiä "neliöttömiä" sanoja, joista tyypillinen esimerkki on ns. 3-symbolinen Thue-sana. Kyseinen sana on siis "neliötä" sisältämätön mutta oikealle ääretön, ja sen alku on

$abcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcb_{\mathbf {} }$.

Tämä 3-symbolinen Thue-sana voidaan muodostaa ns. morfismi-iteroinnin avulla, mikä on sanojen kombinatoriikassa yleinen menetelmä muodostaa vastaavanlaisia sanoja. Tässä tapauksessa morfismi $h$ on seuraava

$a\mapsto abc$

$b\mapsto ac$

$c\mapsto b$

, mikä tarkoittaa siis sitä, että mm. $b$:n kohdalle kirjoitetaan $ac$, jolloin esimerkiksi $h(caba)=h(c).h(a).h(b).h(a)=b.abc.ac.abc=babcacabc$. Morfismin iterointi on vielä aloitettava jostain pisteestä, joka tässä tapauksessa – niin kuin usein muutenkin – on $a$-kirjain. Muodostetaan siis äärellisen pituisia sanoja

$a=h^{\mathbf {0} }(a),h^{\mathbf {1} }(a),h^{\mathbf {2} }(a),h^{\mathbf {3} }(a),h^{\mathbf {4} }(a),...=a,abc,abcacb,abcacbabcbac,abcacbabcbacabcacbacabcb,...$

, sillä $h^{\mathbf {x} }(a)$ tarkoittaa $h$-morfismin soveltamista $a$-kirjaimeen $x$ kertaa, jolloin esimerkiksi

$h^{\mathbf {3} }(a)=h(h(h(a)))=h(h(abc))=h(abc.ac.b)=h(abcacb)=abc.ac.b.abc.b.ac=abcacbabcbac$.

Näin saaduissa äärellisen pituisissa sanoissa aiempi on aina seuraavien prefix, mikä nähdään induktiivisesti, sillä jos induktio-oletuksen mukaan

$h^{\mathbf {x} }(a)\leq h^{\mathbf {x+1} }(a)$ eli $h^{\mathbf {x+1} }(a)=h^{\mathbf {x} }(a).u$ (Missä siis $u_{\mathbf {} }$ on $h^{\mathbf {x+1} }(a)$-sanan loppu sen induktio-oletuksen mukaisen $h^{\mathbf {x} }(a)$-alun jälkeen.), niin

$h^{\mathbf {x+2} }(a)=h(h^{\mathbf {x+1} }(a))=h(h^{\mathbf {x} }(a).u)=h(h^{\mathbf {x} }(a)).h(u)=h^{\mathbf {x+1} }(a).h(u)$, siis $h^{\mathbf {x+2} }(a)=h^{\mathbf {x+1} }(a).h(u)$

mistä taas seuraa, että $h^{\mathbf {x+1} }(a)\leq h^{\mathbf {x+2} }(a)$. Esimerkiksi

$h^{\mathbf {2} }(a)=abcacb=abc.acb=h^{\mathbf {1} }(a).acb$, jolloin $h^{\mathbf {3} }(a)=h(h^{\mathbf {2} }(a))=h(h^{\mathbf {1} }(a).acb)=h(h^{\mathbf {1} }(a)).h(acb)=h^{\mathbf {2} }(a).abcbac$.

Lisäksi induktion perusaskeleena tässä on tietenkin se, että

$h^{\mathbf {0} }(a)=a\leq abc=h^{\mathbf {1} }(a)$.

Iteroiden saadut sanat voidaan siis tulkita saman oikealle äärettömän sanan yhä piteneviksi (On voimassa $\vert h^{\mathbf {x} }(a)\vert <\vert h^{\mathbf {x+1} }(a)\vert$, sillä $h$-morfismi kirjoittaa jokaisen kirjaimen tilalle vähintään yhden kirjaimen, ja lisäksi "iteraatioalkujen" alussa on $a$-kirjain, ja $a$-kirjainten tilalle kirjoitetaan $abc$, mistä seuraa, että "iteraatioalkujen" pituus kasvaa aidosti.) äärellisen pituisiksi aluiksi, jolloin nämä "iteraatioalut" selvällä tavalla määräävät yksikäsitteisen oikealle äärettömän 3-symbolisen Thue-sanan. Tämän x:nnes kirjain määräytyy niin, että katsotaan mikä on $h^{\mathbf {x} }(a)$-"iteraatioalun" x:nnes kirjain. Tässä $h^{\mathbf {x} }(a)$:ää käytettiin siksi, että "iteraatioalku" olisi riittävän pitkä (Onhan $x\leq \vert h^{\mathbf {x} }(a)\vert$.), mutta käytännössä riittää iteroida selvästi vähemmän kuin $x$ kertaa (Oikeastaan helposti nähdään, että $\vert h^{\mathbf {x} }(a)\vert =3\cdot 2^{\mathbf {(x-1)} }$, kun $1\leq x$.).

On syytä huomata, että yllä osoitettiin vain se, että annetun $h$-morfismin $a$-iteroinnilla muodostuu mielekkäällä tavalla oikealle ääretön sana. Sitä tässä ei osoitettu, että kyseinen sana on myös "neliötön", vaan tämän osoittaminen vaatisi oman tarkastelunsa, jota tässä ei esitetä. Erityisesti on syytä huomata se, että yleisestikin morfismiin sijoitettavan sanan "neliöttömyys" ei vielä takaa tuloksen "neliöttömyyttä". Tästä esimerkkinä $h$-morfismi, jossa nyt aiemman sijaan

$a\mapsto ab$

$b\mapsto c$

$c\mapsto acb$

, jota $a$-kirjaimesta iteroiden saataisiin vastaavalla tavalla oikealle ääretön sana, sillä $a\leq h^{\mathbf {1} }(a)$- ja pitenemis-vaatimukset täyttyvät. Kuitenkaan näin saatu sana ei ole "neliötön", sillä vaikka vielä $h^{\mathbf {3} }(a)=abcacb$ on "neliötön", niin $h^{\mathbf {4} }(a)=h(a).h(b).h(c).h(a).h(c).h(b)=abcacbabacbc=abcac.ba.ba.cbc$, eli $h^{\mathbf {4} }(a)$ sisältää $ba$-"neliön". Tällainen "neliön ilmaantuminen" on mahdollista erityisesti siksi, että "ilmaantuvan neliön" ei tarvitse "osua tasan" $h(.)$-"lohkoihin", vaan se voi muodostua myös niiden välissä kuten yllä, missä $ba$-"neliö" muodostui $h(c).h(a).h(c)=acb.ab.acb=ac.ba.ba.cb$-"osuuden" väliin niin, että "osuuden" vasen $ac$-"reuna" ja oikea $cb$-"reuna" eivät ole mukana muodostamassa "neliötä".