Teh­tä­vä:
Li­sää BNF-har­joi­tuk­sia

Tä­mä teh­tä­vä on jat­koa teh­tä­väl­le Backus-Naur Form. Täs­sä teh­tä­väs­sä har­joi­tel­laan yh­teys­riip­pu­mat­to­mien kie­li­op­pien muo­dos­ta­mis­ta ja sel­ven­ne­tään joi­ta­kin yk­si­tyis­koh­tia.

Jos oi­keal­la al­haal­la ole­vaan isoon laa­tik­koon kir­joit­taa kie­li­opin, pie­neen laa­tik­koon kir­joit­taa merk­ki­jo­non, ja pai­naa nap­pia, niin Math­Check piir­tää merk­ki­jo­non jä­sen­nys­puun tai ker­too, et­tä merk­ki­jo­no ei kuu­lu kie­leen. Täs­tä voi ol­la hyö­tyä kun rat­kais­tes­sa­si al­la ole­via teh­tä­viä saat pa­lau­tet­ta, et­tä kie­li­op­pi­si tuot­taa jon­kin merk­ki­jo­non jo­ta ei oli­si pi­tä­nyt tuot­taa.

Al­la on ku­vaus merk­ki­jo­no­jen ja kie­li­op­pien kir­joit­ta­mi­ses­ta Math­Checkil­le. Se ei ole sii­nä sik­si, et­tä opis­ke­li­sit sen ul­koa, vaan sik­si, et­tä kun jäl­jem­pä­nä tar­vit­set yk­si­tyis­koh­tia, voit kat­soa ne sii­tä. Se on myös esi­merk­ki sii­tä, min­kä­lai­sia asioi­ta voi tul­la vas­taan, kun laa­di­taan tark­ka, eri nä­kö­koh­tia huo­mioon ot­ta­va spe­si­fi­kaa­tio näen­näi­ses­ti yk­sin­ker­tai­sel­le asial­le.

Merk­ki­jo­no voi­daan kir­joit­taa Math­Checkil­le muu­ta­mal­la eri ta­val­la:

• Jos se ei ole tyh­jä, sii­nä ei ole vä­li­lyön­te­jä ei­kä ri­vin­siir­to­ja ja jos se ei ala mer­kil­lä " ei­kä ', niin sen voi kir­joit­taa sel­lai­se­naan. Se yl­tää lä­hin­nä seu­raa­vaan vä­li­lyön­tiin, ri­vin­siir­toon tai syöt­teen lop­pu­mi­seen as­ti.
• Jos sii­nä ei ole ri­vin­siir­to­ja ei­kä merk­kiä ", niin sen voi esit­tää merk­kien " ra­jaa­ma­na.
• Jos sii­nä ei ole ri­vin­siir­to­ja ei­kä merk­kiä ', niin sen voi esit­tää merk­kien ' ra­jaa­ma­na.
• Mer­keil­lä " tai ' ra­jat­tu­ja osuuk­sia voi ol­la usei­ta, ja nii­den vä­lis­sä voi ol­la vä­li­lyön­te­jä ja ri­vin­siir­to­ja. Täl­lä ta­val­la merk­ki­jo­non voi ja­kaa useal­le ri­vil­le ja sa­man merk­ki­jo­non si­sään saa yh­tä­ai­kaa merk­ke­jä " ja '.
• Tul­koon täy­del­li­syy­den vuok­si mai­ni­tuk­si, et­tä opet­ta­ja voi käs­keä Math­Checkiä jät­tä­mään merk­ki­jo­noon tar­jo­tut ri­vin­siir­rot huo­miot­ta. Si­ten hän voi esi­mer­kik­si kir­joit­taa merk­ki­jo­non ym­pä­ril­le lai­naus­mer­kit opis­ke­li­jan puo­les­ta, mah­dol­lis­taen tyh­jän merk­ki­jo­non syöt­tä­mi­sen jät­tä­mäl­lä vas­taus­ruu­tu täy­sin tyh­jäk­si. Nor­maa­li­ti­lan­tees­sa opis­ke­li­jan vas­tauk­sen mo­lem­min puo­lin tu­lee au­to­maat­ti­ses­ti ri­vin­siir­rot var­mis­ta­maan, et­tä opet­ta­jan ja opis­ke­li­jan kir­joit­ta­mat teks­ti­al­kiot ei­vät va­hin­gos­sa lii­maan­nu yh­teen. Kun vas­taat al­la ole­viin ky­sy­myk­siin, unoh­da tä­mä mah­dol­li­suus.

Kie­li­op­pi esi­te­tään Math­Checkil­le nol­lal­la tai useam­mal­la vä­li­sym­bo­lin mää­ri­tel­mäl­lä, joi­den pe­räs­sä voi ol­la al­ku­sym­bo­lin ase­tus.

• Vä­li­sym­bo­lin mää­ri­tel­mäs­sä on iso kir­jain, ::= ja yk­si tai useam­pi vaih­to­eh­to. Vaih­to­eh­dot on ero­tet­tu toi­sis­taan pys­ty­vii­val­la |. Vaih­to­eh­to esi­te­tään ku­ten merk­ki­jo­no. Vaih­to­eh­dos­sa esiin­ty­vät isot kir­jai­met tul­ki­taan vä­li­sym­bo­leik­si, ja muut mer­kit esit­tä­vät it­seään. Sa­man vä­li­sym­bo­lin saa mää­ri­tel­lä kor­kein­taan ker­ran. Vä­li­sym­bo­lin saa jät­tää mää­rit­te­le­mät­tä vaik­ka si­tä käy­tet­täi­siin.
• Al­ku­sym­bo­lin ase­tuk­ses­sa on : ja iso kir­jain. Jos al­ku­sym­bo­lin ase­tus puut­tuu, niin vä­li­sym­bo­lien mää­ri­tel­miä on pak­ko ol­la ai­na­kin yk­si, ja en­sim­mäi­se­nä mää­ri­tel­tä­vä vä­li­sym­bo­li on al­ku­sym­bo­li.

Ma­te­maat­ti­ses­sa kir­jal­li­suu­des­sa on ta­pa­na esit­tää ku­kin vä­li­sym­bo­lin mää­ri­tel­mä omal­la ri­vil­lään tai useal­la ri­vil­lä, jois­ta muut kuin en­sim­mäi­nen on si­sen­net­ty. Math­Checkis­sä voi teh­dä niin­kin, mut­ta ol­lak­seen se­kä it­sen­sä et­tä mo­nien oh­jel­moin­ti- yms. kiel­ten kans­sa joh­don­mu­kai­nen, Math­Check sal­lii käyt­tää vä­li­lyön­te­jä ja ri­vin­siir­to­ja va­paas­ti kun­han teks­ti­al­kiot ei­vät me­ne se­kai­sin. Esi­mer­kik­si A::=aB B ::=""|bB toi­mii mut­ta A::=aBB ::=""|bB ei toi­mi, kos­ka toi­nen B ei tu­le tul­ki­tuk­si kie­len B mää­ri­tel­män aluk­si vaan osak­si kie­len A mää­ri­tel­män vii­meis­tä vaih­to­eh­toa.

Kie­li­opin lo­pus­sa on ai­na ;, jot­ta Math­Check ei tul­kit­si­si seu­raa­van ko­men­non al­kua osak­si kie­li­op­pia. Si­nun ei kui­ten­kaan tar­vit­se vä­lit­tää täs­tä, kos­ka opet­ta­ja on kir­joit­ta­nut sen puo­les­ta­si.

Mi­ten Math­Checkin merk­ki­jo­noon saa ri­vin­siir­ron? Vas­tausEi mi­ten­kään. Oli­si sii­hen­kin voi­tu kei­no ke­hit­tää, mut­ta se tus­kin oli­si tuot­ta­nut yh­tä pal­jon pe­da­go­gis­ta hyö­tyä kuin se oli­si tuot­ta­nut vai­vaa ja on­gel­mia. Oli­si mm. pi­tä­nyt kek­siä, mi­ten ri­vin­siir­to piir­re­tään jä­sen­nys­puun sol­muun. Math­Checkin saa jät­tä­mään merk­ki­jo­noon tar­jo­tut ri­vin­siir­rot huo­miot­ta, mut­ta ei saa ot­ta­maan nii­tä mu­kaan. Mi­ten Math­Checkil­le il­mais­taan ε? Vas­taus Tyh­jä merk­ki­jo­no il­mais­taan Math­Checkil­le jo­ko "" tai ''. Ma­te­ma­tii­kas­sa tyh­jää merk­ki­jo­noa mer­ki­tään sym­bo­lil­la ε, mut­ta Math­Checkia ei ole ope­tet­tu tul­kit­se­maan sym­bo­lia ε tyh­jäk­si merk­ki­jo­nok­si. Jos Math­Checkin syöt­tees­sä on ε, niin Math­Check tul­kit­see sen UTF-8-koo­dauk­sen mu­kai­ses­ti kah­den mer­kin mit­tai­sek­si merk­ki­jo­nok­si.

Sa­ma kie­li voi­daan ai­na tuot­taa mo­nel­la eri kie­li­opil­la. Al­la on muu­ta­ma kie­li­op­pi, jot­ka kaik­ki tuot­ta­vat kie­len {ε, a, aa, aaa, …}. Ko­kei­le val­miik­si an­ne­tul­la ja muu­ta­mal­la muul­la merk­ki­jo­nol­la, min­kä­lai­nen jä­sen­nys­puu tu­lee.

Kie­li­op­pi on mo­ni­se­lit­tei­nen, jos ja vain jos jol­la­kin merk­ki­jo­nol­la on kak­si eri jä­sen­nys­puu­ta. Mi­kään lä­hel­lä yl­lä ole­vis­ta kie­li­opeis­ta ei ole mo­ni­se­lit­tei­nen. Esi­mer­kik­si A ::= ε | aaaA | aaA on mo­ni­se­lit­tei­nen, kos­ka se tuot­taa merk­ki­jo­non aaaaaa mo­lem­pien ku­vien mu­kai­ses­ti.

Usein py­ri­tään vält­tä­mään mo­ni­se­lit­tei­syyt­tä. Sen vält­tä­mi­nen on kui­ten­kin jos­kus vai­keaa tai jo­pa mah­do­ton­ta.

Suun­nit­te­le seu­raa­vat kie­li­opit. Aak­kos­to­na on {0, 1}, ja al­ku­sym­bo­lit on an­net­tu val­miik­si. Voit mää­ri­tel­lä va­paas­ti li­sää vä­li­sym­bo­lei­ta.

Mi­ten voit täs­sä lä­hel­lä ole­via työ­ka­lu­ja käyt­täen hel­pos­ti sel­vit­tää, voi­daan­ko os­taa 18 munk­ki­rin­ki­lää ja jos kyl­lä niin mi­ten voi­daan? Vas­tausKo­pioi­mal­la yl­lä ole­va kie­li­op­pi oi­keal­le alas isoon laa­tik­koon, kir­joit­ta­mal­la 18 m-kir­jain­ta pie­neen laa­tik­koon ja pai­na­mal­la vas­taus­nap­pia.

Teh­tä­vä­si on sel­vit­tää suu­rin mää­rä munk­ki­rin­ki­löi­tä, jo­ta ei voi muo­dos­taa os­ta­mal­la so­pi­va yh­dis­tel­mä pak­kauk­sia. Käy­tet­tä­vis­sä­si on kak­si laa­tik­koa, joi­hin kum­paan­kin voit kir­joit­taa kie­li­opin. Kun pai­nat nap­pia, Math­Check ver­taa kie­li­op­pien tuot­ta­mat kie­let (sil­lä ra­joi­tuk­sel­la, et­tä Math­Check ei sel­viä ko­vin mo­ni­mut­kai­sis­ta ta­pauk­sis­ta). Vih­jeKo­pioi edel­li­sen teh­tä­vän kie­li­op­pi mo­lem­piin ruu­tui­hin. Li­sää alem­paan kie­li­op­piin vaih­to­eh­to, jol­la voi os­taa kol­me munk­ki­rin­ki­lää ja su­per­pak­kauk­sen. Laa­di su­per­pak­kauk­sen kie­li­op­pi si­ten, et­tä su­per­pak­kauk­sen ko­ko voi ol­la mi­kä ta­han­sa nol­laa suu­rem­pi mää­rä munk­ki­rin­ki­löi­tä. Vih­je Kun pai­nat nap­pia, Math­Check ker­too, et­tä su­per­pak­kauk­sen avul­la voi os­taa vii­si munk­ki­rin­ki­lää mut­ta il­man si­tä ei voi. Kun kas­va­tat su­per­pak­kauk­sen kans­sa os­tet­ta­vien munk­ki­rin­ki­löi­den mää­rän kol­mes­ta vii­teen, Math­Check ker­too seu­raa­van koon, jon­ka voi os­taa su­per­pak­kauk­sen avul­la mut­ta ei il­man si­tä.

Suun­nit­te­le seu­raa­vat kie­li­opit. Aak­kos­to­na on {a, b}, ja al­ku­sym­bo­lit on an­net­tu val­miik­si. Kun mo­ni­se­lit­tei­syys kiel­le­tään, teh­tä­vät ei­vät muu­tu mah­dot­to­mik­si, mut­ta mel­ko vai­keik­si kyl­lä­kin. Ihan hy­vä, jos saat nä­mä rat­kais­tua mo­ni­se­lit­tei­ses­ti­kin, mut­ta jos kai­paat kun­non haas­tet­ta, niin kiel­lä mo­ni­se­lit­tei­syys.

Lo­puk­si muu­ta­ma asia, jois­sa ai­kai­sem­pien tent­ti­vas­taus­ten pe­rus­teel­la on ol­lut vää­rin­kä­si­tyk­siä.

Jo­kai­nen seu­raa­vis­ta kie­li­opeis­ta tuot­taa tyh­jän kie­len, kos­ka …mis­tään niis­tä ei voi joh­taa merk­ki­jo­noa, jos­sa ei ole vä­li­sym­bo­lei­ta, kos­ka jo­kai­ses­sa vaih­to­eh­dos­sa on ai­na­kin yk­si vä­li­sym­bo­li.

• A ::= A
• A ::= aA
• A ::= B | aB
  B ::= A | bB
• A ::= aAb

Kie­li on (ää­rel­li­nen tai ää­re­tön) jouk­ko merk­ki­jo­no­ja, jois­ta jo­kai­nen on ää­rel­li­nen. Kie­li­op­pi A ::= ε | aA ei tuo­ta ää­re­tön­tä merk­ki­jo­noa aaa… ei­kä jouk­koa {aaa…}. Se tuot­taa ää­ret­tö­män mon­ta eri­lais­ta merk­ki­jo­noa, ni­mit­täin merk­ki­jo­not ε, a, aa, aaa ja niin edel­leen, eli se tuot­taa jou­kon {ε, a, aa, aaa, …} eli {a⁰, a¹, a², a³, …}. Se ei tuo­ta merk­ki­jo­noa aⁿ, mis­sä n on luon­nol­li­nen lu­ku. Se tuot­taa jou­kon {aⁿ | n ∈ ℕ}. Kie­li­op­pi A ::= aAb ei tuo­ta merk­ki­jo­noa aaa…bbb, sil­lä A ::= aAb ei tuo­ta si­tä ei­kä se edes ole merk­ki­jo­no.

Kie­li ei ole kaik­kien merk­ki­jo­no­jen jouk­ko ei­kä edes kaik­kien aak­kos­tos­ta muo­dos­tet­ta­vien merk­ki­jo­no­jen jouk­ko. Kie­li on jouk­ko aak­kos­tos­ta muo­dos­tet­ta­via merk­ki­jo­no­ja eli kaik­kien aak­kos­tos­ta muo­dos­tet­ta­vien merk­ki­jo­no­jen jou­kon osa­jouk­ko.

Ää­rel­li­nen kie­li on kie­li, jos­sa on vain ää­rel­li­nen mää­rä merk­ki­jo­no­ja. Esi­mer­kik­si A ::= aa | aaa mää­rit­te­lee ää­rel­li­sen kie­len, mut­ta A ::= aa | aaaA mää­rit­te­lee ää­ret­tö­män kie­len. Vaik­ka kie­li oli­si ää­re­tön, jo­kai­nen sii­hen kuu­lu­va merk­ki­jo­no on ää­rel­li­nen.

Hup­sis­ta, yl­lä ole­va ku­va ei ole mit­ta­kaa­vas­sa. Jot­kin jou­kot on piir­ret­ty liian isoik­si toi­siin näh­den. Piir­re­tään se uu­des­taan mit­ta­kaa­vaan, jot­ta jouk­ko­jen ko­ko­erot nä­kyi­si­vät oi­kein.

Piir­täi­sin mie­lel­lä­ni myös mit­ta­kaa­vas­sa ole­van ku­van, jos­ta kaik­kien kiel­ten jouk­ko puut­tuu mut­ta muut kol­me ovat mu­ka­na. Va­li­tet­ta­vas­ti en osaa, sil­lä vaik­ka nii­den vä­lil­lä val­lit­se­vat ai­dot osa­jouk­ko­suh­teet ovat ku­ten en­sim­mäi­nen ku­va näyt­tää, ne ovat kes­ke­nään yh­tä­suu­ria. Ää­re­tön jouk­ko to­del­la­kin voi ol­la yh­tä­suu­ri kuin ai­to osa­jouk­kon­sa.

Syy näi­hin on il­miöis­sä, joi­ta tu­tki­taan teh­tä­väs­sä Ra­tio­naa­li­lu­ku­jen jouk­ko on nol­la­mi­tal­li­nen.