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  (kreikkalaisen aakkoston iso sigma-kirjain). Tällöin DNA:n kohdalla  ja bittien kohdalla . Yleensä vaaditaan, että symboliaakkoston on oltava äärellisen kokoinen, ja usein käytetty esimerkki edellisten lisäksi on , 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 -aakkoston kohdalla  on eräs 5-pituinen sana ja  on eräs 10-pituinen sana. Sanoja merkitään usein "sanamuuttujilla" kuten  tai , jolloin  merkitsee -sanan pituutta. Esimerkiksi jos , . 

Tietyn symboliaakkoston  määräämää sanojen joukkoa merkitään , ja siihen kuuluu lisäksi tyhjä sana, jossa ei ole yhtään symbolia (Se on siis 0-pituinen.), ja jota merkitään usein  (kreikkalaisen aakkoston pieni epsilon-kirjain). Selvästi -joukon eri sanoja on (numeroituvasti) ääretön määrä: 0-pituinen tyhjä sana , 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 , missä -"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 ,  ja  merkitsee tuloa,  tai . Selvästi tämä tulo on epäkommutatiivinen (Sillä yleensä .) ja assosiatiivinen (Sillä  suoraan symbolien peräkkäin asettamisesta johtuen, koska  ja  ovat molemmilla puolilla samassa vasemmalta-oikealle-järjestyksessä.). 

Assosiatiivisuudesta johtuen sulkumerkit ovat tuloissa tarpeettomia, eli voidaan merkitä  ja yleisemminkin esimerkiksi . Usein "tulopisteetkin" jätetään merkitsemättä, jolloin äskeinen lyhenee muotoon . Tällä tulo-operaatiolla varustettu -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 , missä -sanoja on peräkkäin n kappaletta. Esimerkiksi jos  ja , niin . Lisäksi määritellään luonnolliseen tapaan, että  ja . 

Myös prefixin käsite on tärkeä. Sana  on sanan  prefix silloin, kun sanan  kirjainjono muodostaa sanan  kirjainjonon alkuosan, mikä merkitään . Esimerkiksi , ja lisäksi :n kaikilla sanoilla  on tietenkin voimassa se, että  ja .

Sanojen kombinatoriikka tutkii mm. seuraavanlaisia kysymyksiä.

Esimerkki 1) Millaisten ehtojen vallitessa sanat kommutoivat, eli . 

On selvää, että sanat  ja  kommutoivat ainakin silloin, jos molemmat ovat saman sanan  potensseja, eli  ja , jolloin . Esimerkiksi jos  ja  ja , . On melko helposti osoitettavissa, että tämä saman -sanan potensseina oleminen on riittävyyden lisäksi myös välttämätön ehto sille, että sanat  ja  kommutoisivat, eli  on sama sana kuin .

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  ja , mutta esimerkiksi jo  eli siinä  on toistuvana "jaksona". Myös yllä esitetty oikealle ääretön sana sisältää "neliön", sillä siinä -"jakso" toistuu peräkkäin kahdesti. Esimerkiksi sana  voi ensisilmäyksellä näyttää "neliöttömältä", mutta se silti sisältää -"jakson" kahdesti peräkkäin, sillä . 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

. 

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  on seuraava

, mikä tarkoittaa siis sitä, että mm. :n kohdalle kirjoitetaan , jolloin esimerkiksi . Morfismin iterointi on vielä aloitettava jostain pisteestä, joka tässä tapauksessa – niin kuin usein muutenkin – on -kirjain. Muodostetaan siis äärellisen pituisia sanoja 

, sillä  tarkoittaa -morfismin soveltamista -kirjaimeen  kertaa, jolloin esimerkiksi

.

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

 eli  (Missä siis  on -sanan loppu sen induktio-oletuksen mukaisen -alun jälkeen.), niin

, siis 

mistä taas seuraa, että . Esimerkiksi

, jolloin .

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

.

Iteroiden saadut sanat voidaan siis tulkita saman oikealle äärettömän sanan yhä piteneviksi (On voimassa , sillä -morfismi kirjoittaa jokaisen kirjaimen tilalle vähintään yhden kirjaimen, ja lisäksi "iteraatioalkujen" alussa on -kirjain, ja -kirjainten tilalle kirjoitetaan , 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 -"iteraatioalun" x:nnes kirjain. Tässä :ää käytettiin siksi, että "iteraatioalku" olisi riittävän pitkä (Onhan .), mutta käytännössä riittää iteroida selvästi vähemmän kuin  kertaa (Oikeastaan helposti nähdään, että , kun .).

On syytä huomata, että yllä osoitettiin vain se, että annetun -morfismin -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ä -morfismi, jossa nyt aiemman sijaan

, jota -kirjaimesta iteroiden saataisiin vastaavalla tavalla oikealle ääretön sana, sillä - ja pitenemis-vaatimukset täyttyvät. Kuitenkaan näin saatu sana ei ole "neliötön", sillä vaikka vielä  on "neliötön", niin , eli  sisältää -"neliön". Tällainen "neliön ilmaantuminen" on mahdollista erityisesti siksi, että "ilmaantuvan neliön" ei tarvitse "osua tasan" -"lohkoihin", vaan se voi muodostua myös niiden välissä kuten yllä, missä -"neliö" muodostui -"osuuden" väliin niin, että "osuuden" vasen -"reuna" ja oikea -"reuna" eivät ole mukana muodostamassa "neliötä".

Lähteet 

  

Kombinatoriikka