Tässä tehtävässä opiskellaan yhteysriippumattomia kielioppeja ja niiden tuottamia kieliä. Kokeile rohkeasti eri alatehtäviä niin paljon kuin haluat ja kokeile myös tahallasi vääriä vastauksia, sillä sekin on usein hyödyksi oppimiselle. Vastaukset tarkastava ohjelma on nimeltään MathCheck. Se ei tiedä kuka olet, eikä se talleta vastauksiasi mihinkään.
Kuvaruudun oikeassa alareunassa olevat laatikot ja napit ovat tarpeen vasta lähellä tämän veppisivun loppua. Älä välitä niistä ennen sitä.
Joidenkin alatehtävien kohdalla on hyvä tietää, että ää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}.
Ensimmäinen tarvitsemamme käsite on merkki. Merkkien joukko vaihtelee tilanteen mukaan. Tässä tehtävässä sallittuja merkkejä ovat numerot, pienet kirjaimet (ei kuitenkaan å, ä ja ö) sekä useimmat välimerkit kuten ! ja jotkut erikoismerkit kuten @. Isot kirjaimet, välilyönti, " ja ; eivät ole sallittuja merkkejä. Jatkossa riittää, että muistat, että isot kirjaimet, välilyönti, " ja ; eivät ole sallittuja merkkejä tässä tehtävässä.
Huomautus: siinä roolissa missä nyt on "", opetuskokeen aikana oli $. Alkuperäinen valinta osoittautui huonoksi ja muutettiin sekä MathCheckissä että tässä tehtävässä. Tätä tehtävää on kuitenkin muutettu vain sen verran kuin oli välttämätöntä jotta se toimisi nykyisellä MathCheckillä; tehtävän narratiivia ei ole päivitetty.
Kun jatkossa käytetään sanaa merkki tarkoitetaan sallittua merkkiä, ellei erikseen ole mainittu että voidaan tarkoittaa myös kiellettyä merkkiä.
Käytössä olevien merkkien joukkoa kutsutaan aakkostoksi (englanniksi alphabet). Aakkostossa voi olla vain sallittuja merkkejä. Aakkosto vaihtelee tapauskohtaisesti. Tässä tehtävässä siis h, 3 ja ? kuuluvat aakkostoon joissakin alatehtävissä ja joissakin toisissa eivät kuulu, mutta H ja " eivät kuulu koskaan.
Yhteysriippumattomien kielioppien yhteydessä merkkejä kutsutaan myös loppusymboleiksi (terminal) syystä, johon tulemme palaamaan.
Kun nolla tai useampia sallittuja merkkejä pannaan peräkkäin, saadaan merkkijono (string) eli sana (word). Merkkijonon pituus on siihen kuuluvien merkkien määrä.
Tyhjä merkkijono todellakin tarkoittaa merkkijonoa, jossa ei ole mitään. Se vaikeuttaa tyhjästä merkkijonosta puhumista. 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ä.
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ä.
Tähän pulmaan on kaksi laajasti käytettyä ratkaisua. Ensimmäisessä merkkijonojen alku ja loppu osoitetaan jotenkin, usein lainausmerkeillä. Silloin äskeisen esimerkin merkkijonot esitetään näin: ”heppa” ja ””. Jos merkkijonot ”an”, ”ana” ja ”s” laitetaan peräkkäin tässä järjestyksessä, ei tule ”an””ana””s” vaan ”ananas”, koska lainausmerkit eivät ole osa itse merkkijonoa vaan keino osoittaa, missä merkkijono alkaa ja missä se loppuu.
Yhteysriippumattomissa kieliopeissa esiintyy usein paljon lyhyitä merkkijonoja. Silloin lainausmerkkejä tulisi niin paljon, että ne häiritsisivät varsinaista asiaa. Siksi on tavallista jättää lainausmerkit pois. Tällöin tyhjä merkkijono esitetään yleensä kreikkalaisella kirjaimella ε, joka luetaan epsilon.
Vastauksissaan MathCheck käyttää tyhjän merkkijonon symbolina "", koska vastaukset esiintyvät usein yhteydessä, jossa lainausmerkkien käyttö on tarpeen. Esimerkiksi seuraava lause on varsin sekava koska lainausmerkit puuttuvat: tärkeitä välimerkkejä ovat ?, !, , ja ..
Matematiikassa ja teoreettisessa tietojenkäsittelytieteessä kieli (language) on joukko merkkijonoja. Ei sen enempää eikä vähempää. Esimerkiksi koira kuuluu suomenkielen sanojen joukkoon, mutta dog ja gfrwwstxq eivät kuulu.
Vaikka tästä kielen käsitteestä puuttuvat sanojen ja lauseiden merkitykset, se ei ole ollenkaan niin tyhjänpäiväinen kuin aluksi saattaa näyttää. Tarkastellaan esimerkiksi kieltä, johon kuuluvat ne ja vain ne epätyhjät numerojonot, joiden esittämä lukuarvo on alkuluku. Ei ole ihan helppoa selvittää, onko annettu luonnollinen luku alkuluku. Hidas keino tämän tehtävän ratkaisemiseksi on tunnettu ainakin antiikin ajoista saakka, mutta taatusti aina kohtuullisen nopea keino keksittiin vasta niinkin myöhään kuin vuonna 2002.
Jos (a) mikä tahansa luonnollinen luku osataan esittää numerojonona ja (b) mistä tahansa merkkijonosta pystytään selvittämään kuuluuko se tähän kieleen, niin pystytään selvittämään, onko mikä tahansa annettu luonnollinen luku alkuluku. Vaihe (a) on hyvin helppo ja tuttu, kuten seuraava alatehtävä havainnollistaa.
Koska (a) on hyvin helppo ja koska (a) ja (b) yhdessä muodostavat keinon ratkaista jossain määrin vaikea tehtävä, täytyy (b):n olla jossain määrin vaikea.
Samanlainen päättely pätee suurelle joukolle muita tehtäviä, jotka ovat erittäin paljon vaikeampia kuin sen selvittäminen, onko annettu luonnollinen luku alkuluku. Siksi tehtävä, kuuluuko annettu merkkijono annettuun kieleen, voi olla äärimmäisen vaativa. Tämä pätee vaikka kielen käsite itsessään on hyvin yksinkertainen — se on vain merkkijonojen jako kahtia: niihin, jotka ovat mukana ja niihin, jotka ovat ulkona.
Avainasemassa tässä on, millä tavalla ”annettu kieli” annetaan. Jotta tietokone voisi etsiä vastausta kysymykseen kuuluuko annettu merkkijono annettuun kieleen, sille pitää tavalla tai toisella antaa sekä merkkijono että kieli. Merkkijonon antamista harjoittelimme edellä. Opimme esittämään jopa tyhjän merkkijonon, vaikka siihen tarvittiinkin vippaskonsti. Kielen esittäminen tietokoneelle on monimuotoinen asia. Aloittakaamme sen pohtiminen esimerkillä.
Pystyimme siis esittämään kolmella jaollisten luonnollisten lukujen kielen tietokoneelle. Kysymys ”onko annettu luonnollinen luku kolmella jaollinen” voidaan nyt ratkaista esittämällä luku numerojonona (mikä on hyvin helppoa, kuten edellä todettiin) ja testaamalla, kuuluuko annettu merkkijono esittämäämme kieleen.
Äärettömien joukkojen teorian avulla voidaan todistaa vastaansanomattomasti, että ei ole eikä voi olla olemassa esitystapaa, joka pystyisi esittämään kaikki kielet. Tunnetaan useita esitystapoja. Toisessa ääripäässä olevat tavat mahdollistavat hyvin tehokkaan käsittelyn tietokoneella, mutta ne pystyvät esittämään vain vähän kieliä. Vastakkaisessa ääripäässä olevat tavat pystyvät esittämään paljon kieliä, mutta moni tarpeellinen asia on mahdoton tehdä tietokoneella.
Yhteysriippumattomat kieliopit sijaitsevat keskialueella. Niillä ei pystytä esittämään kovin paljoa kieliä, mutta pystytään kuitenkin niin paljon, että siitä on suurta hyötyä käytännössä. On kohtalaisen helppoa testata, kuuluuko annettu merkkijono annetun yhteysriippumattoman kieliopin esittämään kieleen. Yhteysriippumattomat kieliopit ovat siis hyvä kompromissi ääripäiden väliltä. Siksi niitä käytetään erittäin paljon tietojenkäsittelyssä.
Valitse jokaiselle vasemman reunan olennolle, onko se merkki (vasen ruutu), onko se merkkijono (keskimmäinen ruutu) ja onko se kieli (oikea ruutu).
| k | |
| {k} | |
| koira | |
| {koira} | |
| koira, kissa, heppa | |
| {koira, kissa, heppa} | |
| ε | |
| {ε} |
Voi tuntua omituiselta, että yksittäinen merkki on samalla merkkijono, mutta yksittäinen merkkijono ei ole kieli (vaikka muuttuu kieleksi, jos sen ympärille lisätään { ja }). Lähtökohtaisesti olento on eri asia kuin kokonaisuus, jonka osana olento on. Joukko-oppi menisi aivan rikki, ellei pidettäisi tiukasti kiinni siitä, että x ≠ {x}.
Lähtökohtaisesti myös merkki ja merkkijono ovat eri asioita. Kun merkkijono esitetään lainausmerkeillä, tämä tulee näkyväksi: a on merkki eikä merkkijono, ja ”a” on merkkijono eikä merkki. Matematiikassa on kuitenkin tapana luopua tällaisista jyrkistä erotteluista silloin kun mahdollista, koska niin on helpompaa. Merkin tulkitseminen merkkijonoksi ei riko mitään mutta helpottaa asioita. Siksi niin on päätetty.
Kun luonnollinen luku jaetaan kolmella kokonaislukujakona, jakojäännös voi saada vain kolme eri vaihtoehtoa: 0, 1 ja 2. Esimerkiksi 7 = 3+3+1, joten 3 menee seitsemään kaksi kertaa ja jakojäännös on 1.
| jaettava | = | osamäärä | kertaa | jakaja | plus | jakojäännös |
| 7 | = | 2 | · | 3 | + | 1 |
| 15 | = | 5 | · | 3 | + | 0 |
| 5 | = | 1 | · | 3 | + | 2 |
Kun luonnollinen luku esitetään numerojonona, niin sen jakojäännös kolmella jaettaessa voidaan laskea käymällä numerot yksitellen läpi, laskemalla kunkin niistä jakojäännös kolmella jaettaessa, ja laskemalla näin saadut luvut yhteen siten että aina kun summa ylittää kakkosen, siitä vähennetään 3. Alla näytetään, miten tällä tavalla saadaan tulokseksi, että luvun 327685 jakojäännös kolmella jaettaessa on 1.
| numerot | 3 | 2 | 7 | 6 | 8 | 5 |
| jakojäännös | 0 | 2 | 1 | 0 | 2 | 2 |
| summa | 0 | 2 | 3 | |||
| 0 | 0 | 2 | 4 | |||
| 1 |
Alla oleva yhteysriippumaton kielioppi hyödyntää tätä periaatetta. Se etenee numerojonossa oikealta vasemmalle eli vastakkaiseen suuntaan kuin äskeisessä esimerkissä edettiin, mutta tämä ei riko periaatetta. Kutakin kieliopissa esiintyvää isoa kirjainta kutsutaan välisymboliksi (nonterminal). Kukin välisymboli edustaa tietynlaisia numerojonoja seuraavasti:
| N | ne numerot, joiden lukuarvon jakojäännös on 0 |
| Y | ne numerot, joiden lukuarvon jakojäännös on 1 |
| K | ne numerot, joiden lukuarvon jakojäännös on 2 |
| A | ne epätyhjät numerojonot, joiden lukuarvon jakojäännös on 0 |
| B | ne epätyhjät numerojonot, joiden lukuarvon jakojäännös on 1 |
| C | ne epätyhjät numerojonot, joiden lukuarvon jakojäännös on 2 |
A ::= N | NA | YC | KB B ::= Y | NB | YA | KC C ::= K | NC | YB | KA N ::= 0 | 3 | 6 | 9 Y ::= 1 | 4 | 7 K ::= 2 | 5 | 8
Pystyviivalla on erotettu toisistaan eri vaihtoehdot, joilla vasemman reunan välisymbolin kieleen kuuluva merkkijono voi muodostua. Esimerkiksi rivi
B ::= Y | NB | YA | KC
tarkoittaa, että kieleen B kuuluva merkkijono muodostuu jollakin seuraavista tavoista:
Luonnollinen luku on kolmella jaollinen, jos ja vain jos sen jakojäännös kolmella jaettaessa on 0. Kolmella jaollisten luonnollisten lukujen kieli on siis välisymbolin A kieli.
Yhteysriippumaton kielioppi esitetään tyypillisesti yhtenä tai useampana välisymbolin määritelmänä. Välisymbolin määritelmässä on ensin iso kirjain, sitten ::= ja lopuksi yksi tai useampi määritelmäjono pystyviivalla | toisistaan erotettuina, kuten tässä esimerkissä:
X ::= "" | aX | bX
Sama iso kirjain saa esiintyä enintään yhden kerran määriteltävänä välisymbolina, siis juuri ennen ::=.
On tapana kirjoittaa kukin välisymbolin määritelmä omalle rivilleen, mutta MathCheck ei vaadi sitä. Sen sijaan MathCheck vaatii, että pystyviiva ja sitä edeltävä määritelmäjono eivät ole kiinni toisissaan. Jos ne ovat kiinni toisissaan, MathCheck tulkitsee pystyviivan osaksi määritelmäjonoa. Jos saat jatkossa käsittämättömiä virheilmoituksia, tarkista, että olet käyttänyt pystyviivaa oikein.
Kokeile, mitä edellisessä alatehtävässä tapahtuu, jos lisäät a:n ja X:n väliin välilyönnin. Osaatko selittää ilmiön? (Ei ole väliä, teetkö lisäyksen alkuperäiselle vai korjatulle kieliopille.)
Määritelmäjono on muuten kuten epätyhjä merkkijono, mutta siinä saa esiintyä aakkoston merkkien lisäksi isoja kirjaimia ja ε. (MathCheckille ε:n sijaan kirjoitetaan "".) (Sana ”määritelmäjono” ei ole yleisessä käytössä. Normaalisti sen sijaan puhutaan merkkijonoista. Silloin kuitenkin käytössä on yhtäaikaa kaksi erilaista merkkijonon käsitettä, aiheuttaen sekaantumisen vaaran.)
Jokainen välisymboli esittää yhtä kieltä. Yksi välisymboleista on alkusymboli (start symbol). Jollei muuta sanota, alkusymboli on ensimmäisenä määritelty välisymboli. MathCheckin voi käskeä käyttämään muuta välisymbolia lisäämällä kieliopin perään kaksoispisteen : ja sen ison kirjaimen, jonka haluaa alkusymboliksi. Älä kirjoita kaksoispistettä välittömästi kiinni edelliseen määritelmäjonoon.
Alussa aakkostosta kiellettiin isot kirjaimet, "", ; ja välilyönti. Olisi ollut mahdollista kehittää vippaskonsteja, joilla nekin olisi voitu sallia. Silloin tämä alaluku olisi muuttunut monimutkaisemmaksi. Se olisi ollut minusta paljon suurempi haitta kuin näiden merkkien kieltäminen.
Isojen kirjainten ja "":n kielto aakkostosta on saanut selityksen: niillä on tärkeä muu tehtävä. Välilyönti on kielletty siksi, että muutoin olisi jotakuinkin mahdotonta suunnitella selkeä kokonaisuus, joka ei perustu lainausmerkkeihin. ; on kielletty siksi, että MathCheck käyttää sitä sisäisesti ilmoittamaan kieliopin loppua. Jollei kieliopilla olisi loppumerkkiä, joissakin tilanteissa olisi mahdotonta antaa järkevää virheilmoitusta. Sinun ei kuitenkaan tarvitse kirjoittaa sitä, koska tehtävissä se on kirjoitettu valmiiksi piiloon vastauksesi perään. (Kyllä, saat kokeilla mitä tapahtuu jos kirjoitat sen.)
Sallittuja merkkejä kutsutaan myös loppusymboleiksi, koska yhteysriippumattoman kieliopin tuottama merkkijono koostuu vain niistä ja koska se on johdonmukaista sanojen alkusymboli ja välisymboli käytön kanssa.
Ensin pitää tietää, mitä tarkoittaa kielten laittaminen peräkkäin. Esittelemme sen esimerkillä, jossa on kolme kieltä:
K, L ja M peräkkäin laitettuna muodostaa kielen, jossa on ne ja vain ne merkkijonot, jotka saadaan valitsemalla mikä tahansa K:n alkio, laittamalla sen perään mikä tahansa L:n alkio ja lopuksi mikä tahansa M:n alkio. Esimerkin kielessä on 12 merkkijonoa seuraavasti:
| K:n alkio | L:n alkio | M:n alkio | lopputulos |
| kana | ε | koppi | kanakoppi |
| kana | ε | va | kanava |
| kana | n | koppi | kanankoppi |
| kana | n | va | kananva |
| kissa | ε | koppi | kissakoppi |
| kissa | ε | va | kissava |
| kissa | n | koppi | kissankoppi |
| kissa | n | va | kissanva |
| koira | ε | koppi | koirakoppi |
| koira | ε | va | koirava |
| koira | n | koppi | koirankoppi |
| koira | n | va | koiranva |
Huomasithan, että ε jätetään pois epätyhjistä lopputuloksista. Jos lopputulokseksi tulee esimerkiksi εε tai εεε, sen paikalle kirjoitetaan ε. Näin tehdään, koska ε ei ole merkki, vaan symboli, joka edustaa sitä merkkijonoa, jossa ei ole yhtään merkkiä.
Määritelmäjonon σ tuottama kieli L(σ) on sen osien tuottamat kielet laitettuna peräkkäin. Osien tuottamat kielet määräytyvät seuraavasti:
Jos välisymbolin A määritelmä on muotoa
A ::= σ1 | σ2 | ⋯ | σn
missä jokainen σi on määritelmäjono, niin L(A) = L(σ1) ∪ L(σ2) ∪ ⋯ ∪ L(σn). Tämä tarkoittaa, että merkkijono kuuluu välisymbolin tuottamaan kieleen jos ja vain jos yksikin välisymbolin määritelmän oikealla puolella esiintyvistä, pystyviivoin toisistaan erotetuista vaihtoehdoista tuottaa ko. merkkijonon.
Yhteysriippumattoman kieliopin tuottama kieli on sen alkusymbolin tuottama kieli.
Välisymbolin määritelmä voi viitata välisymboliin itseensä. (Tätä kutsutaan rekursioksi.) Yksinkertaisin hyödyllinen esimerkki tästä on
A ::= ε | aA.
Nyt selvitämme kielen, jonka A tuottaa.
Kielioppi A ::= A | aA | Aa ei tuota yhtään merkkijonoa. Merkkijonojen tuottaminen ei pääse alkuun, koska siinä ei ole yhtään vaihtoehtoa, joka tuottaisi merkkijonon käyttämättä sen osana A:han kuuluvaa merkkijonoa.
Jatkossa on tehtäviä, joissa sinua pyydetään kirjoittamaan kielioppi. Jos MathCheck ilmoittaa, että kielioppisi tuottaa merkkijonon jota se ei saisi tuottaa, voi olla hyödyllistä saada nähdä, miten kielioppisi sen tuottaa. Sitä varten oikealla alhaalla on keskikokoinen laatikko johon voit syöttää kieliopin, pieni laatikko johon voit syöttää merkkijonon ja kaksi nappia joita painamalla saat jäsennyspuun, jos antamasi merkkijono kuuluu antamasi kieliopin tuottamaan kieleen. Voisi olla hyödyllistä saada apua myös tilanteeseen, jossa kielioppisi jättää tuottamatta jonkin merkkijonon joka sen pitäisi tuottaa, mutta valitettavasti sitä en osaa järjestää.
Vaikka olisit saanut äskeisen alatehtävän heti oikein, jatkon kannalta voi olla hyödyllistä, että harjoittelet oikeassa alareunassa olevien laatikoiden käyttöä. Siksi kopioi kielioppisi keskikokoiseen laatikkoon, kirjoita pieneen laatikkoon jokin kielioppisi tuottamaan kieleen kuuluva merkkijono, ja paina vastausnappia. Muistathan, että saat alkusymbolin vaihdettua lisäämällä loppuun välilyönnin ja esimerkiksi :A.
Kaikki merkkijonot, joissa on joko a:ta tai b:tä mutta ei molempia, saadaan kieliopilla
X ::= A | B
A ::= ε | aA
B ::= b | bB
Huomaathan, että ε tulee X:n kieleen A:n kautta mutta ei B:n kautta? Tämän olisi tietenkin voinut tehdä toisinkin päin, tai ottaa ε mukaan vasta X:ssä, tai ottaa ε mukaan sekä A:n että B:n kautta.
Kaikki merkkijonot, joissa on joko a:ta tai b:tä tai molempia ihan missä järjestyksessä tahansa, saadaan kieliopilla
X ::= ε | aX | bX
Ne merkkijonot, joissa on ensin jokin määrä a:ta ja sitten sama määrä b:tä saadaan näin:
Z ::= ε | aZb
Yhteysriippumattomat kieliopit sopivat hyvin matemaattisten lausekkeiden rakenteen määrittelemiseen. Niitä käytetään paljon myös ohjelmointikielten syntaksin määrittelyssä. Ne ovat niin laaja aihepiiri, että ansaitsevat oman tehtävänsä.