Tässä tehtävässä valmistaudutaan matemaattisiin kieliin sekä ohjelmointikielten kieliopillisiin rakenteisiin liittyvien asioiden opiskeluun tutustumalla joihinkin merkkijonoihin liittyviin asioihin.
Lyhyt MathCheck-ohje (uuteen välilehteen)
Merkkijono on nolla tai useampia merkkejä peräkkäin. Merkit on poimittu jostain joukosta, jota sanotaan aakkostoksi (englanniksi alphabet). Merkkijonoja merkitään usein pienillä kreikkalaisilla kirjaimilla, kuten σ (sigma), ρ (rho) ja δ (delta). Jos aakkostona on pienet kirjaimet, niin esimerkkejä merkkijonoista ovat δ = ero, ρ = li ja σ = maa.
Merkkijonojen liitännäisyyttä voi havainnollistaa kuvalla. Päällekkäisissä kohdissa on aina sama merkki.
σρδσρδσρδσρδσρδ
Ongelmana on siis nähdä, missä merkkijono loppuu. Ohjelmointikielissä yleinen ratkaisu on laittaa merkkijono lainausmerkkeihin, "siis näin". Otamme tämänkin keinon käyttöön, mutta emme ainoana keinona, koska siinä on kaksi ongelmaa.
Numerot ovat "0", "1", "2", "3", "4", "5", "6", "7", "8" ja "9".
Numerot ovat 0, 1, 2, 3, 4, 5, 6, 7, 8 ja 9.
lainausmerkki on ", tiesitkös sen?
Jos sen kirjoittaa näin:
"lainausmerkki on ", tiesitkös sen?"
niin keskellä oleva " lopettaa merkkijonon, joten merkkijonoksi saadaan vain lainausmerkki on .
Jälkimmäinen ongelma on ratkaistu joissakin ohjelmointikielissä käyttämällä merkkiä \ erikoismerkityksessä. Niissä voi kirjoittaa
"lainausmerkki on \", tiesitkös sen?"
Entä jos haluamme merkkijonon sisään molempia rajaajia? Jos haluamme merkkijonoksi vaikka
lainausmerkki on " ja ' on hipsumerkki
Jako metakielen merkkeihin ja kohdekielen merkkeihin on tärkeä. Kohdekielen merkit esiintyvät sellaisinaan merkkijonon sisällössä. Metakielen merkeillä on muu tehtävä. Merkki " on metakielen merkki merkkijonossa "hipsu on '", koska se ei ole osa merkkijonon sisältöä vaan apuväline, jolla merkkijono rajattiin. Merkit h, i, p, s, u, välilyönti, o, n ja ' ovat kohdekielen merkkejä. Merkkijonossa '" ja'" '" ensimmäinen ja toinen ' ovat metakielen ja kolmas ' on kohdekielen merkki. Tämä hahmottuu selvemmin kun kohdekielen merkit esitetään taustavärillä: '" ja'" '".
Jos sanaa ”merkki” tai ”merkkijono” käytetään täsmentämättä, onko kyse meta- vai kohdekielen merkistä tai merkkijonosta, niin yleensä tarkoitetaan kohdekieltä.
Näimme jo edellä sanan aakkosto. Se tarkoittaa kohdekielen merkkien joukkoa. Se vaihtelee tilanteen mukaan. Esimerkiksi luonnollisista luvuista puhuttaessa aakkosto voi koostua merkeistä 0, 1, 2, 3, 4, 5, 6, 7, 8 ja 9. Merkkijono ei välttämättä sisällä kaikkia aakkoston merkkejä. Esimerkiksi merkkijono 40100 esittää luonnollista lukua, mutta ei käytä merkkiä 7.
Merkkijonon pituus on siihen kuuluvien merkkien määrä. Jos sama merkki esiintyy merkkijonossa useasti, se lasketaan pituuteen useasti. Merkkijonon σ pituutta merkitään |σ|. Esimerkiksi |kukka| = 5. Metakielen merkkejä ei lasketa mukaan pituuteen, koska ne eivät ole osa merkkijonon sisältöä vaan ainoastaan sen ilmaisemisessa käytettäviä apuvälineitä.
Äärellinen joukko esitetään usein luettelona aaltosulkeiden välissä tyyliin {1, 2, 3}. Ei ole väliä missä järjestyksessä alkiot luetellaan, joten {3, 1, 2} on sama joukko kuin {1, 2, 3}. On olennaista, esiintyykö alkio vähintään yhden kerran vai ei, mutta ei ole olennaista, esiintyykö alkio kerran, kahdesti vai useammin. Siksi {1, 2, 3, 1} on sama joukko kuin {1, 2, 3} mutta eri joukko kuin {2, 3}.
Kirjoita ilman rajaajia " ja ' ne merkkijonot, joissa on luvun ilmoittama määrä o-kirjainta peräkkäin.
Merkkijono, jossa on nolla merkkiä, tunnetaan nimellä tyhjä merkkijono. Se todellakin tarkoittaa merkkijonoa, jossa ei ole mitään.
Jos merkkijonojen alku ja loppu osoitetaan lainausmerkeillä tai hipsuilla, niin tyhjä merkkijono on helppo kirjoittaa: "" tai ''.
Matematiikassa on tavallista kirjoittaa merkkijonot ilman rajaajia (jolloin ne eivät voi sisältää välilyöntejä). Silloin tyhjän merkkijonon esitystavaksi tulisi ei mitään, eli se minkä kirjoitit ylle nollan o-kirjaimen ruutuun (jos sait sen oikein). Tätä esitystapaa ei kuitenkaan ole otettu käyttöön seuraavan ongelman vuoksi. Lausepari
Merkkijonossa koira esiintyy merkki r. Merkkijonossa heppa ei esiinny merkkiä i.
on ongelmaton, mutta jos merkkijonon heppa tilalle laitetaan tyhjä merkkijono, saadaan
Merkkijonossa koira esiintyy merkki r. Merkkijonossa ei esiinny merkkiä i.
Siitä syntyy vaikutelma, että väitetään, että koira:ssa ei esiinny i:tä, kun tarkoitus oli väittää, että tyhjässä merkkijonossa ei esiinny i:tä.
(Olet ehkä sitä mieltä, että sanan ”ei” edellä pitäisi olla pitempi väli kuin muualla, koska tyhjän merkkijonon molemmilla puolilla pitäisi olla väli. Veppisivun lähdekoodissa siinä onkin, ja siinä on myös komennot, joilla vaihdetaan konekirjoituskirjaimiin ja heti perään takaisin normaaliin. Silti lopputulos näyttää siltä miltä näyttää.)
Tämä ilmiö on toisinaan hyvin hankala. Olisi muun muassa ollut liian vaikeaa rakentaa MathCheck sellaiseksi, että se ei koskaan hämääntyisi sen vuoksi. Siksi sitä ei edes yritetty vaan tyydyttiin kompromissiin, jossa MathCheckin antama virheilmoitus voi olla omituinen silloin, kun vastausruutu on tyhjä.
Symbolin ε kirjoittaminen on siis kömpelöä. On helpompi kirjoittaa "". Siksi MathCheckiä ei ole opetettu tulkitsemaan symbolia ε tyhjäksi merkkijonoksi. Kun sinun pitää kirjoittaa tyhjä merkkijono MathCheckille, niin kirjoita "" tai ''.
Jatkoa varten esitämme matemaattisilla merkinnöillä sen, mitä juuri teimme. Muodostimme kaikki merkkijonot σρ, missä σ ∈ {auto, ammatti} (eli σ oli joko ”auto” tai ”ammatti”) ja ρ ∈ {koulu, kuski} (eli ρ oli poimittu joukosta {koulu, kuski}). Merkkijonojen liittäminen peräkkäin esitetään matematiikassa siis liittämällä niiden symbolit peräkkäin, eli jos σ ja ρ ovat merkkijonoja, niin σρ tarkoittaa sitä merkkijonoa, joka saadaan kirjoittamalla ensin σ:n tarkoittama merkkijono ja välittömästi sen perään ρ:n tarkoittama merkkijono.
Lopuksi teemme minitutkimuksen ja selvitämme, kuinka monta erilaista merkkijonoa voi vähintään ja enintään syntyä, kun poimitaan merkkijono n vaihtoehdosta ja liitetään sen perään merkkijono, joka on poimittu m vaihtoehdosta. Olkoon siis A joukko, jossa on n merkkijonoa, ja B joukko, jossa on m merkkijonoa.
Tuli eri määrä! Siksi ”enintään” ja ”vähintään” tarvitsee tutkia erikseen.
Kun haluamme perustella, että jokin määrä on oikea vastaus ”enintään”-osaan, niin meidän on osoitettava kaksi asiaa.
Tässä tapauksessa syntyy kaikkiaan nm yhdistelmää, joissa ensimmäinen merkkijono on A:sta ja jälkimmäinen B:stä. Kuten edellä nähtiin, ne kaikki eivät ehkä tuota eri merkkijonoja. Varmaa on, että enempää erilaisia merkkijonoja ei voi syntyä, koska ei ole enempää vaihtoehtoja mistä niitä voi syntyä. Siksi enempää ei voida saavuttaa kuin nm.
”Enintään”-tutkimuksessamme jäljellä on kysymys: voidaanko nm saavuttaa? Näimme jo, että tapauksessa n = m = 2 kyllä voidaan, mutta se ei kerro mitä tapahtuu muilla n:n ja/tai m:n arvoilla.
Jos σ alkaa merkillä a, niin myös σρ alkaa a:lla. (Mitä tapahtuu, jos σ = ε?)Kun sanomme, että σ alkaa merkillä a, niin samalla sanomme äänettömästi, että σ ei ole ε. Eli tapaus σ = ε on poissuljettu. Mutta voimmehan silti pohtia mitä siinä tapahtuisi. Silloin σρ alkaa sillä merkillä, millä ρ alkaa paitsi jos vihje2. vihje2ρ = ε Niinpä, jos valitsemme A:n siten, että sen jokainen merkkijono alkaa eri merkillä, niin saamme varmistettua, että kaikki ne vaihtoehdot ovat erilaisia, joissa A:sta poimitaan eri merkkijono. Helpoimmalla pääsemme, jos valitsemme A:n siten, että se koostuu yhden merkin pituisista merkkijonoista.
Jos myös B koostuu yhden merkin pituisista merkkijonoista, niin …kaikki ne vaihtoehdot ovat toisen merkin kohdalta erilaisia, joissa B:stä poimitaan eri merkkijono. Tälle päättelylle on tärkeää, että kaikkien A:n merkkijonojen pituus on 1. Niinpä jos kaksi yhdistelmää poikkeaa A:sta poimitun merkkijonon osalta tai B:stä poimitun merkkijonon osalta, niin ne tuottavat eri merkkijonot. Tällä tavalla saadaan nm vaihtoehtoa.
Olemme osoittaneet, että määrä nm voidaan saavuttaa. Tapaus ”enintään” on valmis.
Tapaus ”vähintään” on helppo silloin, kun n = 0 tai m = 0. Miksi?Silloin nm = 0, joten saadaan enintään 0 merkkijonoa. Se on välttämättä myös vähintään-määrä, koska merkkijonojen määrä ei voi olla vähempää kuin nolla.
Tästä eteenpäin pitkän matkaa rajoitutaan tapaukseen n ≠ 0 ≠ m.
Eräs merkkijono otettiin tarkasteluun kahdesti. Mikä?σ′ρ′ (Tällä ja muutamalla myöhemmällä kohdalla ei ole numeroa, jotta pisteiden saaminen ei olisi liian vaikeaa.)
Osoitamme, että kaikissa muissa tapauksissa σ′ρ ja σρ′ ovat eri merkkijonot. Johtuen siitä miten σ′ valittiin, pätee |σ′| ?≥ |σ|. Johtuen siitä miten ρ′ valittiin, pätee |ρ′| ?≤ |ρ|. Jos |σ′| > |σ|, niin … |σ′ρ| > |σρ| ≥ |σρ′|, joten |σ′ρ| > |σρ′| ja siksi σ′ρ ≠ σρ′. Jos |ρ′| < |ρ|, niin … |σ′ρ| ≥ |σρ| > |σρ′|, joten |σ′ρ| > |σρ′| ja siksi σ′ρ ≠ σρ′. Jäljellä on tapaus |σ′| = |σ| ja |ρ′| = |ρ|. Jos σ′ ≠ σ, niin …σ′ρ ja σρ′ eroavat |σ| ensimmäisen merkin sisällä. Jos ρ′ ≠ ρ, niin …σ′ρ ja σρ′ eroavat |ρ| viimeisen merkin sisällä. Muussa tapauksessa …σ = σ′ ja ρ = ρ′, mikä on se tapaus, joka jo todettiin otetun mukaan kahdesti.
Miksi tapaus σ′ ≠ σ käsiteltiin rajoituksen |σ′| = |σ| alla? Miksi tapaukselle |σ′| > |σ| tehtiin erillinen käsittely, joka kulki aivan eri reittiä kuin tapauksen |σ′| = |σ| ja σ′ ≠ σ käsittely? VastausSiksi, että σ′ ≠ σ ei riitä takaamaan σ′ρ ≠ σρ′ jos |σ′| > |σ|. Näin käy esimerkiksi kun σ′ = maali, ρ = ero, σ = maa ja ρ′ = liero. Tämä vastaesimerkki ei päde siihen miten tapaus |σ′| > |σ| käsiteltiin, koska siellä ρ′:n pitää olla mahdollisimman lyhyt B:n alkio.
Tapaus n ≠ 0 ≠ m on loppuun käsitelty. Tapauksista yhteensä saadaan, että yhteen liittämällä saatavien merkkijonojen määrä on vähintään …n+m−1 kun n ≠ 0 ≠ m ja nolla kun n = 0 tai m = 0.
Mestariluokan tehtävä: onnistuuko nm erilaisen merkkijonon tuottaminen aina silloinkin, kun aakkostossa on vain yksi merkki? Onnistuu valitsemalla A = {ε, a, a2, …, an−1} ja B = {ε, an, a2n, …, a(m−1)n}. Silloin B:n alkioiden pituuserot ovat niin suuret, että edellinen B:n alkio jatkettuna pisimmälläkin A:n alkiolla on lyhyempi kuin seuraava B:n alkio jatkettuna ε:lla.