CFG_set ; CFG_tree

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

Tä­mä teh­tä­vä on jat­koa teh­tä­väl­le Bac­kus-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.

Al­ku­läm­mit­te­lyä

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.

Har­joit­te­lem­me tä­tä! Ko­pioi isoon laa­tik­koon ylim­mäl­le ri­vil­le A ::= 0 | 1 ja toi­sel­le ri­vil­le B ::= A | AB. Kir­joi­ta pik­ku­laa­tik­koon 010 ja pai­na nap­pia. Mi­tä saat? Pi­täi­si tul­la tä­mäThe string "010" is not in the language A.. Vaih­da sit­ten isos­sa laa­ti­kos­sa ylin ja toi­nen ri­vi kes­ke­nään, ja pai­na nap­pia uu­del­leen. Pi­täi­si tul­la tä­mäThe string "010" is in the language B. .

Tul­kit­se edel­li­sen koh­dan jä­sen­nys­puu kie­li­op­pia vas­ten. Toi­sin sa­noen, kat­so mis­sä B on pu­ret­tu au­ki vaih­to­eh­dol­la A ja mis­sä vaih­to­eh­dol­la AB, ja kat­so mis­sä A on pu­ret­tu au­ki vaih­to­eh­dol­la 0 ja mis­sä vaih­to­eh­dol­la 1.

Mik­si tu­los riip­pui ri­vien jär­jes­tyk­ses­tä isos­sa laa­ti­kos­sa? Vas­tausMerk­ki­jo­no 010 kuu­luu kie­leen B mut­ta ei kuu­lu kie­leen A. Jol­lei muu­ta sa­no­ta, BNF-mää­ri­tel­mä ko­ko­nai­suu­te­na tar­koit­taa si­tä kiel­tä, jo­ka mää­ri­tel­lään en­sim­mäi­se­nä. Sik­si kun B:n mää­ri­tel­mä on ylin­nä, vas­tauk­sek­si tu­lee et­tä 010 kuu­luu B:hen se­kä jä­sen­nys­puu, mut­ta kun A:n mää­ri­tel­mä on ylin­nä, vas­tauk­sek­si tu­lee et­tä 010 ei kuu­lu A:han.

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 2 Ol­koon yhä A ::= 0 | 1 ja B ::= A | AB. Ly­hen­ne ”n.y.k.” tar­koit­taa ”nol­lis­ta ja / tai yk­kö­sis­tä koos­tu­vat”. Mit­kä seu­raa­vis­ta pi­tä­vät paik­kan­sa?

	A on kaik­ki n.y.k. jo­not.
	A on kaik­ki n.y.k. epä­tyh­jät jo­not.
	A on kaik­ki n.y.k. jo­not pi­tuu­del­taan 1.
	B on kaik­ki n.y.k. jo­not.
	B on kaik­ki n.y.k. epä­tyh­jät jo­not.
	B on kaik­ki n.y.k. jo­not pi­tuu­del­taan 1.

tai

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 3 Mit­kä seu­raa­vis­ta pi­tä­vät paik­kan­sa?

	A si­säl­tää ai­na­kin kaik­ki n.y.k. jo­not.
	A si­säl­tää ai­na­kin kaik­ki n.y.k. epä­tyh­jät jo­not.
	A si­säl­tää ai­na­kin kaik­ki n.y.k. jo­not pi­tuu­del­taan 1.
	B si­säl­tää ai­na­kin kaik­ki n.y.k. jo­not.
	B si­säl­tää ai­na­kin kaik­ki n.y.k. epä­tyh­jät jo­not.
	B si­säl­tää ai­na­kin kaik­ki n.y.k. jo­not pi­tuu­del­taan 1.

tai

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 5 Mit­kä seu­raa­vis­ta pi­tä­vät paik­kan­sa?

	A si­säl­tää enin­tään kaik­ki n.y.k. jo­not.
	A si­säl­tää enin­tään kaik­ki n.y.k. epä­tyh­jät jo­not.
	A si­säl­tää enin­tään kaik­ki n.y.k. jo­not pi­tuu­del­taan 1.
	B si­säl­tää enin­tään kaik­ki n.y.k. jo­not.
	B si­säl­tää enin­tään kaik­ki n.y.k. epä­tyh­jät jo­not.
	B si­säl­tää enin­tään kaik­ki n.y.k. jo­not pi­tuu­del­taan 1.

tai

ok_text Teit oi­keat va­lin­nat! fail_text Muis­tit­han huo­leh­tia, et­tä tyh­jä merk­ki­jo­no ε tu­li mu­kaan? only_no_yes_on hide_expr 0 = hide_expr 2 Ol­koon C ::= A | ε, ja ol­koon yhä A ::= 0 | 1. (Muis­tat­han, et­tä ma­te­ma­tii­kas­sa tyh­jä merk­ki­jo­no esi­te­tään sym­bo­lil­la ε.) Mit­kä seu­raa­vis­ta si­säl­tä­vät kaik­ki n.y.k. jo­not?

	X ::= A | XA
	X ::= A | XC
	X ::= C | XA
	X ::= C | XC

tai

Mi­ten edel­lä ol­leis­ta kie­li­opeis­ta voi pää­tel­lä, si­säl­tää­kö kie­li kaik­ki n.y.k. jo­not?

X ::= A | XA   Vas­tausA:n kie­li on {0, 1}. Sik­si A ei tuo­ta ε:a. Myös­kään XA ei tuo­ta ε:a, kos­ka jo­kai­nen XA:n tuot­ta­ma merk­ki­jo­no lop­puu jo­hon­kin min­kä A tuot­taa, siis 0:aan tai 1:een. Niin­pä A | XA ei tuo­ta ε:a.

X ::= A | XC   Vas­taus Ku­ten edel­lä to­det­tiin, A ei tuo­ta ε:a. Jot­ta XC tuot­tai­si ε:n, pi­tää se­kä X:n et­tä C:n tuot­taa ε. C tuot­taa sen. X:n koh­dal­la syn­tyy mu­na-ka­na-on­gel­ma: X tuot­taa ε:n jos XC tuot­taa ε:n, ja XC tuot­taa ε:n jos X tuot­taa ε:n. BNF:ssä vain sel­lai­nen tuot­ta­mi­nen mer­kit­see, jos­sa ei ole mu­ka­na jos­sit­te­lua. Sik­si X ei tuo­ta ε:a. (Sa­ma pe­rus­te­lu oli­si kel­van­nut edel­li­ses­sä koh­das­sa.) Li­sä­tie­toaTä­mä koh­ta poik­keaa edel­li­ses­tä si­kä­li, et­tä jo­kai­nen merk­ki­jo­no jo­ka voi­daan tuot­taa, voi­daan tuot­taa ää­ret­tö­män mo­nel­la eri ta­val­la. Jos jo­kin merk­ki­jo­no on tuo­tet­tu jol­lain ta­val­la, voi­daan se tuot­taa uu­del­leen yh­tä as­kel­ta pi­tem­mäl­lä ta­val­la sään­nöl­lä X ::= A | XC va­lit­se­mal­la se X:ksi ja tuot­ta­mal­la C:stä ε.

X ::= C | XA   Vas­tausTyh­jä merk­ki­jo­no saa­daan va­lit­se­mal­la oi­keal­ta puo­lel­ta C ja sen tuo­tok­sis­ta ε. Mi­kä ta­han­sa muu merk­ki­jo­no saa­daan re­kur­sii­vi­ses­ti. En­sin tuo­te­taan sen muut mer­kit pait­si vii­mei­nen. Tä­mä tu­los va­li­taan oi­kean puo­len X:ksi, ja vii­mei­nen merk­ki tuo­te­taan A:sta.

X ::= C | XC   Vas­tausEdel­li­sen koh­dan vas­taus kel­paa tä­hän si­ten muu­tet­tu­na, et­tä vii­mei­nen merk­ki tuo­te­taan XC:n C:stä.

Kie­li­op­pien kir­joit­ta­mi­nen Math­Checkil­le

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. Ko­kei­le oi­keal­la al­haal­la kum­pi­kin näis­tä kie­li­opeis­ta merk­ki­jo­nol­la abb.

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.

Har­joi­tel­laan hie­man tie­don esiin kai­va­mis­ta spe­si­fi­kaa­tios­ta. Mää­rit­te­le kie­li O, jo­hon ei kuu­lu yh­tään merk­ki­jo­noa. Sen voi teh­dä ai­na­kin kah­del­la eri ta­val­la.
ok_text On­nek­si ol­koon! Olet on­nis­tu­nees­ti mää­ri­tel­lyt tyh­jän kie­len! Tä­tä saa­vu­tus­ta kel­paa esi­tel­lä su­ku­lai­sil­le! CFG_set :O; CFG_set2 ; CFG_compare tai

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­Checkiä 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.

Mo­ni­se­lit­tei­set kie­li­opit

Jos kie­li voi­daan tuot­taa mil­lään kie­li­opil­la, niin se voi­daan 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.

A ::= ε | Aa
A ::= ε | aA
A ::= ε | a | aAa
A ::= ε | a | Aaa
A ::= BC   B ::= ε | a | aa   C ::= ε | aaCa
aaaaaaa tai

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. Aluk­si sal­li mo­ni­se­lit­tei­syys. Sit­ten kiel­lä se ja pa­ran­na kie­li­op­pia kun­nes Math­Check hy­väk­syy sen.

Ne jo­not, jois­sa ei ole mis­sään koh­das­sa yk­kö­sen pe­räs­sä nol­la. ok_text Oi­kein! CFG_set X ::= NY N ::= "" | 0N Y ::= "" | 1Y ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
X ::= ; CFG_compare tai

Ne jo­not, jois­sa on ai­na­kin yk­si yk­kö­nen ei­kä ole mis­sään koh­das­sa yk­kö­sen pe­räs­sä nol­la. ok_text Oi­kein! CFG_set X ::= NY N ::= "" | 0N Y ::= 1 | 1Y ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
X ::= ; CFG_compare tai

Ne jo­not, jois­sa on ai­na­kin yk­si 0 ja ai­na­kin yk­si 1. ok_text Oi­kein! CFG_set X ::= 0Y1Y | 1Y0Y Y ::= "" | 0Y | 1Y ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
X ::= ; CFG_compare tai

Ne jo­not, jois­sa ei ole mis­sään koh­das­sa 0:n pe­räs­sä 0. ok_text Oi­kein! CFG_set E ::= F | F0 F ::= "" | F1 | F01 ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
E ::= ; CFG_compare tai

Ne jo­not, jois­sa on jos­sa­kin koh­das­sa 0:n pe­räs­sä 0. ok_text Oi­kein! CFG_set N ::= 00 | 0N | 1N | N0 | N1 ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
N ::= ; CFG_compare tai

Ne pa­rit­to­man pi­tui­set jo­not, joi­den kes­kel­lä on 1. ok_text Oi­kein! CFG_set Y ::= 1 | MYM M ::= 0 | 1 ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
Y ::= ; CFG_compare tai

Ne pa­rit­to­man pi­tui­set jo­not, joi­den en­sim­mäi­nen, kes­kim­mäi­nen ja vii­mei­nen merk­ki ovat sa­ma. ok_text Oi­kein! CFG_set P ::= 0 | 1 | 0N0 | 1Y1 N ::= 0 | MNM Y ::= 1 | MYM M ::= 0 | 1 ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
P ::= ; CFG_compare tai

Li­sää kie­li­op­pien suun­nit­te­lua

Kir­joi­ta kie­li­op­pi ko­kous­ajoil­le. Ko­kous­ajas­sa on päi­vä­mää­rä, al­ka­mis­ai­ka ja lo­pe­tus­ai­ka. Ajat on ero­tet­tu toi­sis­taan -:lla. Päi­vä­mää­rän ja ai­ko­jen vä­lis­sä on ai­na­kin yk­si vä­li­lyön­ti. Päi­vä­mää­rä voi ol­la muo­toa pp.kk.vvvv, mut­ta päi­vän ja kuu­kau­den saa il­moit­taa myös yh­del­lä nu­me­rol­la. Kel­lon­ajat ovat muo­toa h:mm:ss tai hh:mm:ss. Älä kir­joi­ta nu­me­roi­ta 0, 1, 2, …, 9, vaan käy­tä nii­den si­jaan vä­li­kiel­tä N. Se on an­net­tu pii­los­sa val­mii­na. (Se käyt­tää vain yh­tä nu­me­roa, jot­ta Math­Check ei tu­keh­tui­si.) Jos ha­luat, niin mää­rit­te­le en­sin apu­kie­li P edus­ta­maan päi­vä­mää­riä ja K edus­ta­maan kel­lon­ai­ko­ja. Vas­taus­laa­ti­kon ala­puo­lel­ta va­li­taan, min­kä kie­len Math­Check tar­kas­taa. CFG_set X ::= PVK-K V ::= ' ' | ' V' P ::= Y.Y.NNNN Y ::= N | NN K ::= N:NN:NN | NN:NN:NN N ::= 1 ; CFG_set2
X ::= N ::= 1 ; X P K CFG_compare tai

Kir­joi­ta kie­li­op­pi kie­lel­le, jos­sa on kaik­ki kir­jai­mes­ta c koos­tu­vat jo­not, joi­den pi­tuus ei ole kol­mel­la jaol­li­nen, ja vain ne. ok_text On­nis­tuit! CFG_set C ::= c | cc | Cccc ; CFG_set2
C ::= ; CFG_compare tai

Munk­ki­rin­ki­löi­tä myy­dään nel­jän ja seit­se­män kap­pa­leen pak­kauk­sis­sa. Kir­joi­ta kie­li­op­pi kie­lel­le, jos­sa on täs­mäl­leen ne kir­jai­mes­ta m koos­tu­vat jo­not, joil­le on mah­dol­lis­ta os­taa jo­non pi­tuu­den il­mai­se­ma mää­rä munk­ki­rin­ki­löi­tä. ok_text Kyl­lä! CFG_set M ::= "" | mmmmM | mmmmmmmM ; CFG_set2
M ::= ; CFG_compare tai

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. Jat­ko­ky­sy­mysMi­ten voi­daan hel­pos­ti kir­joit­taa 18 m-kir­jain­ta niin et­tä ei tu­le va­hin­gos­sa 17 tai 19? Vas­tausKir­joit­ta­mal­la 6 m-kir­jain­ta, maa­laa­mal­la ja ko­pioi­mal­la se, ja pu­dot­ta­mal­la se maa­la­tun pääl­le kol­mes­ti.

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­je1Ko­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­je2 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ä.

ok_text Kie­li­opit tuot­ta­vat sa­man kie­len. fail_text Kie­li­opit tuot­ta­vat eri kie­let. CFG_set ; CFG_set2 ; CFG_compare tai

Mi­kä on suu­rin mää­rä munk­ki­rin­ki­löi­tä, jo­ta ei voi muo­dos­taa?
only_no_yes_on ok_text Niin on! f_nodes 1 hide_expr 17= tai

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. (Saat mer­ka­ta näis­tä pis­teet jos saat ne rat­kais­tua mo­ni­se­lit­tei­ses­ti.)

Ne merk­ki­jo­not, jois­sa on sa­ma mää­rä a:ta kuin b:tä. Vih­jeMää­rän saat sa­mak­si käyt­tä­mäl­lä vain vaih­to­eh­to­ja, jois­sa a esiin­tyy yh­tä mon­ta ker­taa kuin b. Ra­ken­na vas­taus­ta vä­hi­tel­len ja an­na Math­Checkin ker­toa mi­tä vie­lä puut­tuu. Jos py­rit yk­si­se­lit­tei­syy­teen, niin kan­nat­taa mää­ri­tel­lä kie­li, jos­sa on täs­mäl­leen ne merk­ki­jo­not, jois­sa va­sem­mal­ta luet­taes­sa b:n mää­rä ei mis­sään koh­das­sa yli­tä a:n mää­rää ja on lo­puk­si sa­ma. ok_text Jee! CFG_set S ::= "" | aSbS | bSaS ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
S ::= ; CFG_compare tai

Ne merk­ki­jo­not, jois­sa on vä­hem­män a:ta kuin b:tä. Vih­jeJos­sa­kin koh­das­sa on yli­mää­räi­nen b. Si­tä en­nen on sa­ma mää­rä a:ta kuin b:tä. Sen jäl­keen­kin saat­taa ol­la jo­ta­kin. ok_text Hie­no vas­taus! CFG_set V ::= SbS | SbV S ::= "" | aSbS | bSaS ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
V ::= ; CFG_compare tai

Ne merk­ki­jo­not, jois­sa on eri mää­rä a:ta kuin b:tä. Vih­jeOn eri mää­rä jos ja vain jos on vä­hem­män tai enem­män. ok_text Ji­huu! CFG_set E ::= V | W V ::= SbS | SbV W ::= SaS | SaW S ::= "" | aSbS | bSaS ;
Kiel­lä mo­ni­se­lit­tei­syys CFG_set2
E ::= ; CFG_compare tai

It­sen­sä mää­rit­te­le­mis­har­joi­tuk­sia

Kir­joi­ta kie­li­op­pi M Math­Checkin merk­ki­jo­noil­le olet­taen, et­tä vä­li­lyön­ti, " ja ' edus­ta­vat it­seään, ja m edus­taa mi­tä ta­han­sa muu­ta merk­kiä jo­ka voi tul­la ky­see­seen. Jot­ta teh­tä­vä ei oli­si liian vai­kea, jä­tä huo­miot­ta teks­ti­al­kioi­den vä­li­nen tyh­jä ti­la ja mer­kin $ eri­kois­teh­tä­vä.

Jos ha­luat, niin mää­rit­te­le en­sin apu­kie­li S edus­ta­maan sel­lai­se­naan kir­joi­tet­tua merk­ki­jo­noa, L edus­ta­maan mer­keil­lä " ra­jat­tua merk­ki­jo­noa tai merk­ki­jo­non osaa, ja H edus­ta­maan mer­keil­lä ' ra­jat­tua merk­ki­jo­noa tai merk­ki­jo­non osaa. Vas­taus­laa­ti­kon ala­puo­lel­ta va­li­taan, min­kä kie­len Math­Check tar­kas­taa. ok_text Näin se käy, kun sen osaa! CFG_set M ::= S | X S ::= m | Sm | S" | S' X ::= H | L | XH | XL H ::= "'A'" A ::= "" | " A" | mA | '"A' L ::= '"B"' B ::= "" | " B" | mB | "'B" ; CFG_set2
; M S L H CFG_compare tai

Kir­joi­ta kie­li­op­pi Math­Checkin kie­li­opeil­le olet­taen, et­tä v edus­taa mi­tä ta­han­sa vä­li­sym­bo­lia (eli isoa kir­jain­ta) ja m edus­taa mi­tä ta­han­sa ky­see­seen tu­le­vaa merk­ki­jo­noa (myös nii­tä, jois­sa käy­te­tään vä­li­sym­bo­lei­ta). Jot­ta teh­tä­vä ei oli­si liian vai­kea, esi­tä teks­ti­al­kioi­den vä­li­nen tyh­jä ti­la ai­na täs­mäl­leen yh­del­lä vä­li­lyön­nil­lä, älä­kä edes yri­tä esit­tää si­tä, et­tä sa­maa vä­li­sym­bo­lia ei saa mää­ri­tel­lä kah­des­ti. ok_text Tä­mä ei ol­lut­kaan yh­tä työ­läs kuin edel­li­nen! CFG_set K ::= ": v" | W | "W : v" W ::= V | "W V" V ::= "v ::= A" A ::= m | "m | A" ; CFG_set2
K ::= ; CFG_compare tai

Lo­puk­si

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

Jo­kai­nen merk­ki­jo­no on ää­rel­li­nen. Esi­mer­kik­si a, aa ja aaa ovat merk­ki­jo­no­ja, mut­ta aaa… ei ole. On ole­mas­sa ää­ret­tö­mien merk­ki­jo­no­jen teo­ria, mut­ta BNF ei kä­sit­te­le si­tä ei­kä tä­mä kurs­si myös­kään.

Kie­li on jouk­ko merk­ki­jo­no­ja. Kie­li voi ol­la ää­rel­li­nen tai ää­re­tön. Jäl­kim­mäi­ses­sä ta­pauk­ses­sa kie­les­sä on ää­ret­tö­män mon­ta merk­ki­jo­noa, mut­ta jo­kai­nen niis­tä on ää­rel­li­nen. Esi­mer­kik­si kie­les­sä {ε, a, aa, aaa, …} on ää­ret­tö­män mon­ta merk­ki­jo­noa.

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ä. Se ei 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 tut­ki­taan teh­tä­väs­sä Ra­tio­naa­li­lu­ku­jen jouk­ko on nol­la­mi­tal­li­nen.