Teh­tä­vä:
Merk­ki­jo­not

Täs­sä teh­tä­väs­sä val­mis­tau­du­taan ma­te­maat­ti­siin kie­liin se­kä oh­jel­moin­ti­kiel­ten kie­lio­pil­li­siin ra­ken­tei­siin liit­ty­vien asioi­den opis­ke­luun tu­tus­tu­mal­la joi­hin­kin merk­ki­jo­noi­hin liit­ty­viin asioi­hin.

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Merk­ki, merk­ki­jo­no ja aak­kos­to

Merk­ki­jo­no on nol­la tai useam­pia merk­ke­jä pe­räk­käin. Mer­kit on poi­mit­tu jos­tain jou­kos­ta, jo­ta sa­no­taan aak­kos­tok­si (eng­lan­nik­si alphabet). Merk­ki­jo­no­ja mer­ki­tään usein pie­nil­lä kreik­ka­lai­sil­la kir­jai­mil­la, ku­ten σ (sigma), ρ (rho) ja δ (delta). Jos aak­kos­to­na on pie­net kir­jai­met, niin esi­merk­ke­jä merk­ki­jo­nois­ta ovat δ = ero, ρ = li ja σ = maa.

Merk­ki­jo­no­jen pe­rus­ope­raa­tio on pe­räk­käin liit­tä­mi­nen. Jos σ, ρ ja δ ovat ku­ten äs­ken, niin σρ = maali. Se on esi­mer­kik­si re­mon­toi­jil­le ja ur­hei­li­joil­le tut­tu sa­na. Pe­räk­käin liit­tä­mi­nen ei ole vaih­dan­nais­ta. Se tar­koit­taa, et­tä on mah­dol­lis­ta, et­tä σρ ≠ ρσ. Esi­mer­kik­si ρσ ei ole­kaan maali, vaan ρσ = Se­kin on ur­hei­li­joil­le tut­tu sa­na.
tai

Pe­räk­käin liit­tä­mi­nen on lii­tän­näis­tä. Se tar­koit­taa, et­tä ovat­pa σ, ρ ja δ mi­tä merk­ki­jo­no­ja ta­han­sa, niin (σρ)δ = σ(ρδ). Jos δ = ero, ρ = li ja σ = maa, niin σρ = maali ku­ten jo näim­me. Kat­so­jat toi­vo­vat, et­tä (σρ)δ:n il­mai­se­ma kä­si­te oli­si oman jouk­kueen hy­väk­si, sil­lä (σρ)δ = (älä lai­ta sul­ku­ja). Toi­saal­ta ρδ = , jo­ten σ(ρδ) = . Sii­tä huo­li­mat­ta, et­tä merk­ki­jo­no­jen (σρ)δ ja σ(ρδ) suo­men­kie­len mu­kai­ses­ti tul­ki­tut mer­ki­tyk­set ei­vät eh­kä ol­leet sa­mat, merk­ki­jo­noi­na (σρ)δ ja σ(ρδ) oli­vat kui­ten­kin täy­sin sa­mat.
tai

Merk­ki­jo­no­jen lii­tän­näi­syyt­tä voi ha­vain­nol­lis­taa ku­val­la. Pääl­lek­käi­sis­sä koh­dis­sa on ai­na sa­ma merk­ki.

σρδ

σρ
δ

σ
ρ
δ

σ
ρδ

σρδ

Seu­raa­vak­si on rat­kais­ta­va eräs merk­ki­jo­no­jen esit­tä­mi­seen liit­ty­vä on­gel­ma. Jot­ta huo­mai­sit on­gel­man, kir­joi­ta vas­taus­ruu­tuun hauva ja klikkaa vastausnappia.
tai

On­gel­ma­na on siis näh­dä, mis­sä merk­ki­jo­no lop­puu. Oh­jel­moin­ti­kie­lis­sä ylei­nen rat­kai­su on lait­taa merk­ki­jo­no lai­naus­merk­kei­hin, "siis näin". Otam­me tä­män­kin kei­non käyt­töön, mut­ta em­me ai­noa­na kei­no­na, kos­ka sii­nä on kak­si on­gel­maa.

Jäl­kim­mäi­nen on­gel­ma on rat­kais­tu jois­sa­kin oh­jel­moin­ti­kie­lis­sä käyt­tä­mäl­lä merk­kiä \ eri­kois­mer­ki­tyk­ses­sä. Niis­sä voi kir­joit­taa

"lainausmerkki on \", tiesitkös sen?"

Tä­mä rat­kai­su on kui­ten­kin tä­män­het­ki­siin tar­pei­siim­me liian se­ka­va. Sik­si teem­me toi­sin: merk­ki­jo­no­jen ra­jaa­ji­na saa käyt­tää myös merk­kiä '. Kir­joi­ta yl­lä ole­va esi­merk­ki.
tai

En­tä jos ha­luam­me merk­ki­jo­non si­sään mo­lem­pia ra­jaa­jia? Jos ha­luam­me merk­ki­jo­nok­si vaik­ka

lainausmerkki on " ja ' on hipsumerkki

On­nis­tuu! Lai­naus­mer­keil­lä ja/tai hip­su­mer­keil­lä ra­jat­tu­ja merk­ki­jo­no­ja saa lait­taa pe­räk­käin. Niit­ten vä­lis­sä saa (mut­ta ei ole pak­ko) ol­la vä­li­lyön­te­jä ja/tai ri­vin­siir­to­ja. Lop­pu­tu­los tul­ki­taan yh­dek­si merk­ki­jo­nok­si. Kir­joi­ta yl­lä ole­va esi­merk­ki.
tai

Sil­loin kun merk­ki­jo­nois­sa on mui­ta merk­ke­jä kuin kir­jai­mia ja nu­me­roi­ta, lai­naus­mer­kit merk­ki­jo­no­jen ym­pä­ril­lä saat­ta­vat ol­la eduk­si luet­ta­vuu­del­le. Esi­mer­kik­si seu­raa­va lau­se on var­sin se­ka­va kos­ka lai­naus­mer­kit puut­tu­vat: tär­kei­tä vä­li­merk­ke­jä ovat ?, !, , ja .. Esi­tä sen lop­pu ky­sy­mys­mer­kis­tä al­kaen lop­pu­pis­te mu­kaan lu­kien si­ten, et­tä käy­tät lai­naus­merk­ke­jä lau­seen mer­ki­tyk­sen kan­nal­ta jär­ke­vis­sä koh­dis­sa. Math­Check tar­vit­see ko­ko vas­tauk­se­si ym­pä­ril­le hip­sut, mut­ta ne on an­net­tu val­mii­na.
tai

Lii­ko­jen lai­naus­merk­kien on­gel­man rat­kai­sem­me sal­li­mal­la merk­ki­jo­non kir­joit­ta­mi­sen il­man ra­jaa­jia, jos se täyt­tää tie­tyt eh­dot. Eh­dot ovat sel­lai­set, et­tä se­kä ih­mi­nen et­tä tie­to­ko­ne tun­nis­taa, mi­kä esi­tys­ta­pa on käy­tös­sä ja mi­kä merk­ki­jo­no on ky­sees­sä. Ne ovat seu­raa­vat (käy­tä jo­kai­ses­sa koh­das­sa ra­jaa­jia, sil­lä nyt nii­tä ei ole an­net­tu val­mii­na): tai

Ja­ko me­ta­kie­len merk­kei­hin ja koh­de­kie­len merk­kei­hin on tär­keä. Koh­de­kie­len mer­kit esiin­ty­vät sel­lai­si­naan merk­ki­jo­non si­säl­lös­sä. Me­ta­kie­len mer­keil­lä on muu teh­tä­vä. Merk­ki " on me­ta­kie­len merk­ki merk­ki­jo­nos­sa "hipsu on '", kos­ka se ei ole osa merk­ki­jo­non si­säl­töä vaan apu­vä­li­ne, jol­la merk­ki­jo­no ra­jat­tiin. Mer­kit h, i, p, s, u, vä­li­lyön­ti, o, n ja ' ovat koh­de­kie­len merk­ke­jä. Merk­ki­jo­nos­sa '" ja'" '" en­sim­mäi­nen ja toi­nen ' ovat me­ta­kie­len ja kol­mas ' on koh­de­kie­len merk­ki. Tä­mä hah­mot­tuu sel­vem­min kun koh­de­kie­len mer­kit esi­te­tään taus­ta­vä­ril­lä: '" ja'" '".

Jos sa­naa ”merk­ki” tai ”merk­ki­jo­no” käy­te­tään täs­men­tä­mät­tä, on­ko ky­se me­ta- vai koh­de­kie­len mer­kis­tä tai merk­ki­jo­nos­ta, niin yleen­sä tar­koi­te­taan koh­de­kiel­tä.

Näim­me jo edel­lä sa­nan aak­kos­to. Se tar­koit­taa koh­de­kie­len merk­kien jouk­koa. Se vaih­te­lee ti­lan­teen mu­kaan. Esi­mer­kik­si luon­nol­li­sis­ta lu­vuis­ta pu­hut­taes­sa aak­kos­to voi koos­tua mer­keis­tä 0, 1, 2, 3, 4, 5, 6, 7, 8 ja 9. Merk­ki­jo­no ei vält­tä­mät­tä si­säl­lä kaik­kia aak­kos­ton merk­ke­jä. Esi­mer­kik­si merk­ki­jo­no 40100 esit­tää luon­nol­lis­ta lu­kua, mut­ta ei käy­tä merk­kiä 7.

Merk­ki­jo­non pi­tuus on sii­hen kuu­lu­vien merk­kien mää­rä. Jos sa­ma merk­ki esiin­tyy merk­ki­jo­nos­sa useas­ti, se las­ke­taan pi­tuu­teen useas­ti. Merk­ki­jo­non σ pi­tuut­ta mer­ki­tään |σ|. Esi­mer­kik­si |kukka| = 5. Me­ta­kie­len merk­ke­jä ei las­ke­ta mu­kaan pi­tuu­teen, kos­ka ne ei­vät ole osa merk­ki­jo­non si­säl­töä vaan ai­noas­taan sen il­mai­se­mi­ses­sa käy­tet­tä­viä apu­vä­li­nei­tä.

Ää­rel­li­nen jouk­ko esi­te­tään usein luet­te­lo­na aal­to­sul­kei­den vä­lis­sä tyy­liin {1, 2, 3}. Ei ole vä­liä mis­sä jär­jes­tyk­ses­sä al­kiot lue­tel­laan, jo­ten {3, 1, 2} on sa­ma jouk­ko kuin {1, 2, 3}. On olen­nais­ta, esiin­tyy­kö al­kio vä­hin­tään yh­den ker­ran vai ei, mut­ta ei ole olen­nais­ta, esiin­tyy­kö al­kio ker­ran, kah­des­ti vai useam­min. Sik­si {1, 2, 3, 1} on sa­ma jouk­ko kuin {1, 2, 3} mut­ta eri jouk­ko kuin {2, 3}.

Kir­joi­ta ly­hin mah­dol­li­nen merk­ki­jo­no, jo­ka esit­tää jou­kon, jo­hon kuu­luu lu­ku 8 ja vain se.
tai

Kir­joi­ta ai­na­kin 6 merk­kiä pit­kä merk­ki­jo­no, jo­ka esit­tää jou­kon, jo­hon kuu­luu lu­ku 8 ja vain se. Aak­kos­to ei si­säl­lä vä­li­lyön­tiä.
tai

Kir­joi­ta jouk­ko {7,7,2,7,2,5,7,2,7} mah­dol­li­sim­man ly­hye­nä merk­ki­jo­no­na.
tai

Mit­kä mer­kit aak­kos­tos­sa täy­tyy ai­na­kin ol­la, jot­ta lu­ku­jouk­ko­ja voi­tai­siin esit­tää täl­lä ta­val­la? Jos et kek­si tar­peek­si mon­taa vas­taus­ta, älä jä­tä mi­tään koh­taa tyh­jäk­si vaan lai­ta sa­ma vas­taus mo­neen koh­taan, jot­ta vir­he­il­moi­tus oli­si hel­pom­pi ym­mär­tää.
tai

Täs­sä koh­das­sa koh­de­kie­len mer­keik­si hy­väk­sy­tään a ja vä­li­lyön­ti. Kir­joi­ta merk­ki­jo­no, jon­ka pi­tuus on 5 ja jos­sa ei ole kah­ta a:ta pe­räk­käin.
tai

Mi­kä oli aak­kos­to edel­li­ses­sä koh­das­sa?
{, } tai

Va­lit­se oi­keat vaih­to­eh­dot.
Jo­kai­nen merk­ki on merk­ki­jo­no. Vih­jeJos py­säh­dyit miet­ti­mään tä­tä, niin olet hy­väs­sä seu­ras­sa. Oh­jel­moin­ti­kie­lis­sä C ja C++ merk­ki on eri asia kuin merk­ki­jo­no, jos­sa on ko. merk­ki ei­kä muu­ta. Merk­ki esi­te­tään tyy­liin 'a' ja merk­ki­jo­no "a". Ver­tai­lu if( 'a' == "a" ) ei kel­paa kään­tä­jäl­le. Sik­si vas­taus voi­si ol­la ei.

Merk­ki­jo­no­jen teo­rias­sa tut­ki­taan kui­ten­kin si­tä ta­paus­ta, jos­sa ne kat­so­taan sa­mak­si. Tä­mä nä­kyy mer­kin­tä­ta­vas­ta. Jos merk­ki­jo­no esi­te­tään il­man ra­jaa­jia ja sii­nä on yk­si merk­ki, niin esi­tys ei mi­ten­kään eroa sii­tä, et­tä esi­te­tään se ai­noa merk­ki. Jos ha­lut­tai­siin kat­soa yh­den mer­kin merk­ki­jo­no eri asiak­si kuin sen ai­noa merk­ki, niin pi­täi­si va­li­ta esi­tys­ta­vat, jois­sa ne myös näyt­tä­vät eri­lai­sil­ta. (Niin­hän C++:ssa on teh­ty.)
Jo­kai­nen merk­ki­jo­no on merk­ki. Vih­jeMerk­ki­jo­no "ab" ei ole merk­ki.
Merk­ki­jo­non "oho" pi­tuus on 2, kos­ka sii­nä esiin­tyy ta­san kah­ta eri merk­kiä, ni­mit­täin o ja h. Vih­jeMerk­ki­jo­non "oho" pi­tuus on 3. Sen en­sim­mäi­nen merk­ki on o, toi­nen h ja kol­mas o. Jos ky­syt­täi­siin kuin­ka mon­ta eri merk­kiä on merk­ki­jo­nos­sa "oho", niin 2 oli­si oi­kea vas­taus.
"karuselli" ja "karu" "selli" tar­koit­ta­vat Math­Checkil­le sa­maa merk­ki­jo­noa. Vih­jeNiin edel­lä sa­not­tiin, kun ker­rot­tiin, et­tä hip­suil­la ja/tai lai­naus­mer­keil­lä ra­jat­tu­ja merk­ki­jo­no­ja voi liit­tää pe­räk­käin ja tu­los tul­ki­taan yh­dek­si merk­ki­jo­nok­si.
Merk­ki­jo­noon si­säl­ty­viä vä­li­lyön­te­jä ei las­ke­ta merk­ki­jo­non pi­tuu­teen. Vih­jeVä­li­lyön­nit ovat merk­ke­jä sii­nä mis­sä muut­kin, jo­ten myös ne las­ke­taan merk­ki­jo­non pi­tuu­teen.
tai

Tyh­jä merk­ki­jo­no

Kir­joi­ta il­man ra­jaa­jia " ja ' ne merk­ki­jo­not, jois­sa on lu­vun il­moit­ta­ma mää­rä o-kir­jain­ta pe­räk­käin.

4 tai
2 tai
0 tai

Merk­ki­jo­no, jos­sa on nol­la merk­kiä, tun­ne­taan ni­mel­lä tyh­jä merk­ki­jo­no. Se to­del­la­kin tar­koit­taa merk­ki­jo­noa, jos­sa ei ole mi­tään.

Jos merk­ki­jo­no­jen al­ku ja lop­pu osoi­te­taan lai­naus­mer­keil­lä tai hip­suil­la, niin tyh­jä merk­ki­jo­no on help­po kir­joit­taa: "" tai ''.

Ma­te­ma­tii­kas­sa on ta­val­lis­ta kir­joit­taa merk­ki­jo­not il­man ra­jaa­jia (jol­loin ne ei­vät voi si­säl­tää vä­li­lyön­te­jä). Sil­loin tyh­jän merk­ki­jo­non esi­tys­ta­vak­si tu­li­si ei mi­tään, eli se min­kä kir­joi­tit yl­le nol­lan o-kir­jai­men ruu­tuun (jos sait sen oi­kein). Tä­tä esi­tys­ta­paa ei kui­ten­kaan ole otet­tu käyt­töön seu­raa­van on­gel­man vuok­si. Lau­se­pa­ri

Merk­ki­jo­nos­sa koira esiin­tyy merk­ki r. Merk­ki­jo­nos­sa heppa ei esiin­ny merk­kiä i.

on on­gel­ma­ton, mut­ta jos merk­ki­jo­non heppa ti­lal­le lai­te­taan tyh­jä merk­ki­jo­no, saa­daan

Merk­ki­jo­nos­sa koira esiin­tyy merk­ki r. Merk­ki­jo­nos­sa ei esiin­ny merk­kiä i.

Sii­tä syn­tyy vai­ku­tel­ma, et­tä väi­te­tään, et­tä koira:ssa ei esiin­ny i:tä, kun tar­koi­tus oli väit­tää, et­tä tyh­jäs­sä merk­ki­jo­nos­sa ei esiin­ny i:tä.

(Olet eh­kä si­tä miel­tä, et­tä sa­nan ”ei” edel­lä pi­täi­si ol­la pi­tem­pi vä­li kuin muual­la, kos­ka tyh­jän merk­ki­jo­non mo­lem­mil­la puo­lil­la pi­täi­si ol­la vä­li. Vep­pi­si­vun läh­de­koo­dis­sa sii­nä on­kin, ja sii­nä on myös ko­men­not, joil­la vaih­de­taan ko­ne­kir­joi­tus­kir­jai­miin ja he­ti pe­rään ta­kai­sin nor­maa­liin. Sil­ti lop­pu­tu­los näyt­tää sil­tä mil­tä näyt­tää.)

Tä­mä il­miö on toi­si­naan hy­vin han­ka­la. Oli­si muun muas­sa ol­lut liian vai­keaa ra­ken­taa Math­Check sel­lai­sek­si, et­tä se ei kos­kaan hä­mään­tyi­si sen vuok­si. Sik­si si­tä ei edes yri­tet­ty vaan tyy­dyt­tiin komp­ro­mis­siin, jos­sa Math­Checkin an­ta­ma vir­he­il­moi­tus voi ol­la omi­tui­nen sil­loin, kun vas­taus­ruu­tu on tyh­jä.

Tyh­jä merk­ki­jo­no esi­te­tään ma­te­ma­tii­kas­sa yleen­sä kreik­ka­lai­sel­la kir­jai­mel­la ε, jo­ka lue­taan ep­si­lon. No niin, kir­joi­ta­pas seu­raa­vaan ruu­tuun ε! Ei­kö näp­päi­mis­tös­sä­si ole sel­lais­ta näp­päin­tä? Kei­no­ja on kyl­lä ole­mas­sa. Windowsis­sa ⟨Alt⟩+238 pi­täi­si toi­mia kun­han NumLock on pääl­lä. Linuxis­sa pi­täi­si toi­mia ⟨CTRL⟩+⟨SHIFT⟩+u 03b5 ⟨ENTER⟩. Help­poa, var­sin­kin noi­den koo­dien 238 ja 03b5 muis­ta­mi­nen! Sym­bo­lin voi myös maa­la­ta, ko­pioi­da ja pu­dot­taa, jos en­sin on­nis­tuu sen jos­tain löy­tä­mään.
tai

Sym­bo­lin ε kir­joit­ta­mi­nen on siis köm­pe­löä. On hel­pom­pi kir­joit­taa "". Sik­si Math­Checkiä ei ole ope­tet­tu tul­kit­se­maan sym­bo­lia ε tyh­jäk­si merk­ki­jo­nok­si. Kun si­nun pi­tää kir­joit­taa tyh­jä merk­ki­jo­no Math­Checkil­le, niin kir­joi­ta "" tai ''.

Kir­joi­ta tyh­jä merk­ki­jo­no.
tai

Muual­la kuin Math­Checkin vas­taus­ruu­duis­sa ε tar­koit­taa tyh­jää merk­ki­jo­noa. Jos siis si­nun pi­tää kir­joit­taa ε Math­Checkil­le, niin se tar­koit­taa, et­tä si­nun pi­tää kir­joit­taa tyh­jä merk­ki­jo­no Math­Checkil­le. Kir­joi­ta ε.
tai

Tä­män pi­täi­si ol­la help­po. Kaik­ki tar­vit­ta­vat sym­bo­lit on se­li­tet­ty edel­lä.
|ε| = tai

Va­lit­se oi­keat vaih­to­eh­dot.
ε on tyh­jän merk­ki­jo­non sym­bo­li ma­te­ma­tii­kas­sa, mut­ta ei Math­Checkin syö­te­kie­les­sä.
"" on merk­ki.
ε on merk­ki.
ε on me­ta­kie­len merk­ki.
ε on koh­de­kie­len merk­ki.
Merk­ki­jo­nos­sa ε ei ole yh­tään merk­kiä.
Jos σ on merk­ki­jo­no, niin εσ tar­koit­taa sa­maa merk­ki­jo­noa.
tai

Merk­ki­jo­no­jen liit­tä­mi­nen pe­räk­käin

Muo­dos­ta kaik­ki merk­ki­jo­not, jot­ka saa­daan ot­ta­mal­la yk­si merk­ki­jo­nois­ta an, ana ja s; lait­ta­mal­la sen pe­rään jom­pi­kum­pi jäl­jel­le jää­neis­tä; ja li­sää­mäl­lä lop­puun vii­mei­sek­si jäl­jel­le jää­nyt. Jos et kek­si tar­peek­si mon­taa vas­taus­ta, älä jä­tä mi­tään koh­taa tyh­jäk­si vaan lai­ta sa­ma vas­taus mo­neen koh­taan, jot­ta vir­he­il­moi­tus oli­si hel­pom­pi ym­mär­tää.

tai

Muo­dos­ta kaik­ki merk­ki­jo­not, jot­ka saa­daan ot­ta­mal­la al­ku­osak­si auto tai ammatti ja lop­pu­osak­si koulu tai kuski.

tai

Jat­koa var­ten esi­täm­me ma­te­maat­ti­sil­la mer­kin­nöil­lä sen, mi­tä juu­ri teim­me. Muo­dos­tim­me kaik­ki merk­ki­jo­not σρ, mis­sä σ ∈ {auto, ammatti} (eli σ oli jo­ko ”auto” tai ”ammatti”) ja ρ ∈ {koulu, kuski} (eli ρ oli poi­mit­tu jou­kos­ta {koulu, kuski}). Merk­ki­jo­no­jen liit­tä­mi­nen pe­räk­käin esi­te­tään ma­te­ma­tii­kas­sa siis liit­tä­mäl­lä nii­den sym­bo­lit pe­räk­käin, eli jos σ ja ρ ovat merk­ki­jo­no­ja, niin σρ tar­koit­taa si­tä merk­ki­jo­noa, jo­ka saa­daan kir­joit­ta­mal­la en­sin σ:n tar­koit­ta­ma merk­ki­jo­no ja vä­lit­tö­mäs­ti sen pe­rään ρ:n tar­koit­ta­ma merk­ki­jo­no.

Nyt ta­voit­tee­na on sel­vit­tää, kuin­ka pit­kä merk­ki­jo­no syn­tyy, kun tun­ne­tun pi­tui­sen merk­ki­jo­non pe­rään lii­te­tään tun­ne­tun pi­tui­nen merk­ki­jo­no. Täy­den­nä tau­luk­ko.
ekan pi­tuusto­kan pi­tuustu­lok­sen pi­tuus
72
04
nm
tai

Lo­puk­si teem­me mi­ni­tut­ki­muk­sen ja sel­vi­täm­me, kuin­ka mon­ta eri­lais­ta merk­ki­jo­noa voi vä­hin­tään ja enin­tään syn­tyä, kun poi­mi­taan merk­ki­jo­no n vaih­to­eh­dos­ta ja lii­te­tään sen pe­rään merk­ki­jo­no, jo­ka on poi­mit­tu m vaih­to­eh­dos­ta. Ol­koon siis A jouk­ko, jos­sa on n merk­ki­jo­noa, ja B jouk­ko, jos­sa on m merk­ki­jo­noa.

Edel­lä näim­me, et­tä jos A = {auto, ammatti} ja B = {koulu, kuski}, niin syn­tyy nel­jä vaih­to­eh­toa. Siis ta­pauk­ses­sa n = m = 2 voi syn­tyä 4 vaih­to­eh­toa. Tut­ki­kaam­me toi­nen­kin ta­paus, jos­sa n = m = 2. Ol­koon A = {koulu, koululais} ja B = {kuri, laiskuri}. Mit­kä merk­ki­jo­not saa­daan liit­tä­mäl­lä A:sta poi­mi­tun merk­ki­jo­non pe­rään B:stä poi­mit­tu merk­ki­jo­no?


tai

Tu­li eri mää­rä! Sik­si ”enin­tään” ja ”vä­hin­tään” tar­vit­see tut­kia erik­seen.

Kun ha­luam­me pe­rus­tel­la, et­tä jo­kin mää­rä on oi­kea vas­taus ”enin­tään”-osaan, niin mei­dän on osoi­tet­ta­va kak­si asiaa.

Täs­sä ta­pauk­ses­sa syn­tyy kaik­kiaan nm yh­dis­tel­mää, jois­sa en­sim­mäi­nen merk­ki­jo­no on A:sta ja jäl­kim­mäi­nen B:stä. Ku­ten edel­lä näh­tiin, ne kaik­ki ei­vät eh­kä tuo­ta eri merk­ki­jo­no­ja. Var­maa on, et­tä enem­pää eri­lai­sia merk­ki­jo­no­ja ei voi syn­tyä, kos­ka ei ole enem­pää vaih­to­eh­to­ja mis­tä nii­tä voi syn­tyä. Sik­si enem­pää ei voi­da saa­vut­taa kuin nm.

”Enin­tään”-tut­ki­muk­ses­sam­me jäl­jel­lä on ky­sy­mys: voi­daan­ko nm saa­vut­taa? Näim­me jo, et­tä ta­pauk­ses­sa n = m = 2 kyl­lä voi­daan, mut­ta se ei ker­ro mi­tä ta­pah­tuu muil­la n:n ja/tai m:n ar­voil­la.

Jos σ al­kaa mer­kil­lä a, niin myös σρ al­kaa a:lla. (Mi­tä ta­pah­tuu, jos σ = ε?)Kun sa­nom­me, et­tä σ al­kaa mer­kil­lä a, niin sa­mal­la sa­nom­me ää­net­tö­mäs­ti, et­tä σ ei ole ε. Eli ta­paus σ = ε on pois­sul­jet­tu. Mut­ta voim­me­han sil­ti poh­tia mi­tä sii­nä ta­pah­tui­si. Sil­loin σρ al­kaa sil­lä mer­kil­lä, mil­lä ρ al­kaa pait­si jos vih­je2. vih­je2ρ = ε Niin­pä, jos va­lit­sem­me A:n si­ten, et­tä sen jo­kai­nen merk­ki­jo­no al­kaa eri mer­kil­lä, niin saam­me var­mis­tet­tua, et­tä kaik­ki ne vaih­to­eh­dot ovat eri­lai­sia, jois­sa A:sta poi­mi­taan eri merk­ki­jo­no. Hel­poim­mal­la pää­sem­me, jos va­lit­sem­me A:n si­ten, et­tä se koos­tuu yh­den mer­kin pi­tui­sis­ta merk­ki­jo­nois­ta.

Jos myös B koos­tuu yh­den mer­kin pi­tui­sis­ta merk­ki­jo­nois­ta, niin kaik­ki ne vaih­to­eh­dot ovat toi­sen mer­kin koh­dal­ta eri­lai­sia, jois­sa B:stä poi­mi­taan eri merk­ki­jo­no. Täl­le päät­te­lyl­le on tär­keää, et­tä kaik­kien A:n merk­ki­jo­no­jen pi­tuus on 1. Niin­pä jos kak­si yh­dis­tel­mää poik­keaa A:sta poi­mi­tun merk­ki­jo­non osal­ta tai B:stä poi­mi­tun merk­ki­jo­non osal­ta, niin ne tuot­ta­vat eri merk­ki­jo­not. Täl­lä ta­val­la saa­daan nm vaih­to­eh­toa.

Olem­me osoit­ta­neet, et­tä mää­rä nm voi­daan saa­vut­taa. Ta­paus ”enin­tään” on val­mis.

Ta­paus ”vä­hin­tään” on help­po sil­loin, kun n = 0 tai m = 0. Mik­si?Sil­loin nm = 0, jo­ten saa­daan enin­tään 0 merk­ki­jo­noa. Se on vält­tä­mät­tä myös vä­hin­tään-mää­rä, kos­ka merk­ki­jo­no­jen mää­rä ei voi ol­la vä­hem­pää kuin nol­la.

Täs­tä eteen­päin pit­kän mat­kaa ra­joi­tu­taan ta­pauk­seen n ≠ 0 ≠ m.

Mer­kin­tä an tar­koit­taa merk­ki­jo­noa, jos­sa on n a:ta pe­räk­käin ei­kä muu­ta. An­na seu­raa­vat merk­ki­jo­not.
a3
a1
a0

tai

Eri yh­dis­tel­mien mää­rä saa­daan an­ne­tuil­la n:n ja m:n (nol­las­ta poik­kea­vil­la) ar­voil­la mel­ko pie­nek­si va­lit­se­mal­la A = {a0, a1, a2, …, a} eli A = {ε, a, a2, …, a} ja B = {ε, a, a2, …, a}.
tai

Sil­loin yh­dis­tel­mik­si tu­le­vat kaik­ki pel­käs­tään a:sta koos­tu­vat merk­ki­jo­not, joi­den pi­tuus on vä­hin­tään ja enin­tään . Nii­tä on yh­teen­sä eri­lais­ta.
tai

Vie­lä tar­vit­see to­dis­taa, et­tä tä­tä vä­hem­pää ei voi saa­vut­taa mil­lään epä­tyh­jil­lä jou­koil­la A ja B (epä­tyh­jil­lä, kos­ka ole­tim­me n ≠ 0 ≠ m, mis­sä n ja m tar­koit­ta­vat A:n ja B:n ko­ko­ja.) Si­tä var­ten ol­koon ρ′ mah­dol­li­sim­man ly­hyt B:n al­kio. (Jos on mon­ta vaih­to­eh­toa, niin ei ole vä­liä mi­kä niis­tä va­li­taan.) Tar­kas­te­lem­me merk­ki­jo­no­ja σρ′, mis­sä σ käy lä­pi kaik­ki A:n al­kiot. Tar­kas­te­lem­me yh­teen­sä ta­paus­ta. Niis­tä jo­kai­ses­ta tu­lee eri merk­ki­jo­no, kos­ka kun σ saa kak­si eri ar­voa, niin myös σρ′ saa kak­si eri ar­voa. Vih­je 1Kuin­ka mon­ta eri merk­ki­jo­noa ρ′ käy tar­kas­te­lus­sa lä­pi? Vih­je 2ρ′ käy tar­kas­te­lus­sa lä­pi yh­den merk­ki­jo­non. Va­lit­tiin et­tä ρ′ on mah­dol­li­sim­man ly­hyt, ja jos se jät­ti usei­ta vaih­to­eh­to­ja, niin va­lit­tiin niis­tä jo­kin. Vih­je 3Kuin­ka mon­ta eri merk­ki­jo­noa σ käy tar­kas­te­lus­sa lä­pi? Vih­je 4σ käy tar­kas­te­lus­sa lä­pi yh­den merk­ki­jo­non jo­kais­ta A:n al­kio­ta koh­ti. Mi­kä muut­tu­ja otet­tiin käyt­töön esit­tä­mään A:n al­kioi­den mää­rää? Vih­je 5Kun ρ′ käy tar­kas­te­lus­sa lä­pi yh­den merk­ki­jo­non ja σ n merk­ki­jo­noa, niin kuin­ka mon­ta yh­dis­tel­mää ρ′σ käy­dään lä­pi?
tai

Ol­koon σ′ mah­dol­li­sim­man pit­kä A:n al­kio. (Jos on mon­ta vaih­to­eh­toa, niin ei ole vä­liä mi­kä niis­tä va­li­taan.) Tar­kas­te­lem­me merk­ki­jo­no­ja σ′ρ, mis­sä ρ käy lä­pi kaik­ki B:n al­kiot. Tar­kas­te­lem­me yh­teen­sä ta­paus­ta. Niis­tä jo­kai­ses­ta tu­lee eri merk­ki­jo­no, kos­ka kun ρ saa kak­si eri ar­voa, niin myös σ′ρ saa kak­si eri ar­voa.
tai

Eräs merk­ki­jo­no otet­tiin tar­kas­te­luun kah­des­ti. Mi­kä?σ′ρ′ (Täl­lä ja muu­ta­mal­la myö­hem­mäl­lä koh­dal­la ei ole nu­me­roa, jot­ta pis­tei­den saa­mi­nen ei oli­si liian vai­keaa.)

Osoi­tam­me, et­tä kai­kis­sa muis­sa ta­pauk­sis­sa σ′ρ ja σρ′ ovat eri merk­ki­jo­not. Joh­tuen sii­tä mi­ten σ′ va­lit­tiin, pä­tee |σ′| ? |σ|. Joh­tuen sii­tä mi­ten ρ′ va­lit­tiin, pä­tee |ρ′| ? |ρ|. Jos |σ′| > |σ|, niin |σ′ρ| > |σρ| ≥ |σρ′|, jo­ten |σ′ρ| > |σρ′| ja sik­si σ′ρ ≠ σρ′. Jos |ρ′| < |ρ|, niin |σ′ρ| ≥ |σρ| > |σρ′|, jo­ten |σ′ρ| > |σρ′| ja sik­si σ′ρ ≠ σρ′. Jäl­jel­lä on ta­paus |σ′| = |σ| ja |ρ′| = |ρ|. Jos σ′ ≠ σ, niin σ′ρ ja σρ′ eroa­vat |σ| en­sim­mäi­sen mer­kin si­säl­lä. Jos ρ′ ≠ ρ, niin σ′ρ ja σρ′ eroa­vat |ρ| vii­mei­sen mer­kin si­säl­lä. Muus­sa ta­pauk­ses­sa σ = σ′ ja ρ = ρ′, mi­kä on se ta­paus, jo­ka jo to­det­tiin ote­tun mu­kaan kah­des­ti.

Mik­si ta­paus σ′ ≠ σ kä­si­tel­tiin ra­joi­tuk­sen |σ′| = |σ| al­la? Mik­si ta­pauk­sel­le |σ′| > |σ| teh­tiin eril­li­nen kä­sit­te­ly, jo­ka kul­ki ai­van eri reit­tiä kuin ta­pauk­sen |σ′| = |σ| ja σ′ ≠ σ kä­sit­te­ly? Vas­tausSik­si, et­tä σ′ ≠ σ ei rii­tä ta­kaa­maan σ′ρ ≠ σρ′ jos |σ′| > |σ|. Näin käy esi­mer­kik­si kun σ′ = maali, ρ = ero, σ = maa ja ρ′ = liero. Tä­mä vas­ta­esi­merk­ki ei pä­de sii­hen mi­ten ta­paus |σ′| > |σ| kä­si­tel­tiin, kos­ka siel­lä ρ′:n pi­tää ol­la mah­dol­li­sim­man ly­hyt B:n al­kio.

Kuin­ka mon­ta eri merk­ki­jo­noa muo­toa σ′ρ ja/tai σρ′ kai­ken kaik­kiaan saa­tiin?
tai

Ta­paus n ≠ 0 ≠ m on lop­puun kä­si­tel­ty. Ta­pauk­sis­ta yh­teen­sä saa­daan, et­tä yh­teen liit­tä­mäl­lä saa­ta­vien merk­ki­jo­no­jen mää­rä on vä­hin­tään n+m−1 kun n ≠ 0 ≠ m ja nol­la kun n = 0 tai m = 0.

Mes­ta­ri­luo­kan teh­tä­vä: on­nis­tuu­ko nm eri­lai­sen merk­ki­jo­non tuot­ta­mi­nen ai­na sil­loin­kin, kun aak­kos­tos­sa on vain yk­si merk­ki? On­nis­tuu va­lit­se­mal­la A = {ε, a, a2, …, an−1} ja B = {ε, an, a2n, …, a(m−1)n}. Sil­loin B:n al­kioi­den pi­tuus­erot ovat niin suu­ret, et­tä edel­li­nen B:n al­kio jat­ket­tu­na pi­sim­mäl­lä­kin A:n al­kiol­la on ly­hyem­pi kuin seu­raa­va B:n al­kio jat­ket­tu­na ε:lla.