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. [1]
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
- ↑ http://domino.utu.fi/tiedotus/tiedotukset.nsf/61345dc704eae28ac22568bd00428706/61fab16a713b8b10c22573ef00377305?OpenDocument[vanhentunut linkki]