Teht. 1 (M.V.) yht. 12p a) 5p Muodostetaan tilasiirtymätaulukko, jossa alkutilasta {1} lähtien a- ja b-syötteitä tutkien päätellään kaikki saavutettavissa olevat 7 tilaa. - tilasiirtymäkaavio ei välttämätön, mutta jos on, niin vastattava taulukkoa - alkutila ja kaikki hyväksyvät lopputilat oltava merkittyinä - puuttuva tai virheellinen tila ja siirtymät: -0.5 - -1 p - pelkästään determinisoinnin tulos ilman välivaiheita: enintään 2p b) 4p Jaetaan tilat kahteen joukkoon: 1) hyväksyvät lopputilat (5 tilaa) ja 2) muut (2 tilaa). Jaetaan joukko 2 kahteen osaan, koska siirtymät erilaiset. - alkuperäinen jako väärin: -1p - alkuperäinen jako oikein mutta ei ositettu ollenkaan: 2p - tiloja ei ositettu riittävästi/ositettu liikaa: -2p/-1p - osittain virheellinen ositus ilman välivaiheita: 1p - oikea idea mutta suuria virheitä: 1p - automaatti piirrettävä tässä tai c-kohdassa c) 3p Poistetaan b-kohdan automaatista yksi tila kerrallaan, kunnes säännöllinen lauseke voidaan lukea. - oikea lauseke ja selitys: 3p - välivaiheet esitetty mutta lopputuloksessa pieniä puutteita: 2.5p - väärä lauseke ja selitys, ei välivaiheita: 0p Teht. 2 Kukin kohta 3p, yht. 9p Kontekstiton kielioppi 1.5p/kohta ja säännöllisyyden/säännöttömyyden osoitus 1.5p/kohta. Pelkkä maininta säännöllinen/epäsäännöllinen ilman perusteluja: 0p; perustelu esim. maininta, että voidaan toteuttaa äärellisellä automaatilla: 0.5p a) Kieli on äärellinen ja siten säännöllinen. b) Epäsäännöllinen, koska a:n määrä pitäisi pystyä muistamaan. - Pumppauslemmatodistus ei välttämätön, jos ymmärretty, että äärellisellä automaatilla ei ole kielen tunnistamiseen tarvittavaa muistia. - Pumppauslemmatodistus muuten oikein, mutta pumpattu väärä määrä ja väitetty ettei esim. a^(n-j)b^n kuulu kieleen: -0.5p c) Kieli on säännöllinen. Säännöllinen lauseke esim. (aa)*b(bb)*. - pelkkä maininta mahdollisuudesta tehdä äärellinen automaatti: 0p --- Teht. 3 (W.H.) Kukin kohta max 2 p, yht. 6p a) Muodostetaan kummastakin lausekkeesta epsilonautomaatit, poistetaan epsilonit, determinisoidaan ja minimoidaan. Jos olivat ekvivalentit, niin lopputulosautomaatit ovat tilojen nimiä lukuunottamatta samat. - ei haitannut jos puuttui epsilonien poisto - jos kerrottu vain, että tehdään automaatit ja verrataan, niin 1p - jos kerrottu vain, että tehdään automaatit ja minimoidaan, niin 1.5p - jos ehdotettu matemaattista todistusta (lausekkeiden sievennystä, jos saisi samoiksi), niin 0.5p; jos lisäksi kerrottu, miten äärellinen kieli tutkittaisiin, niin yht. 1p - jos muuten ok (muodostettu autom., det. ja min.), mutta ei tiedä, että lopputulokset identtiset (ehdotettu automaattien vertailua erilaisilla syötteillä, joita yl. tap. äärettömän monta!), niin 1p b) G on oikealle lineaarinen, joten siitä voidaan muodostaa äärellinen automaatti. Sitten toimutaan kuten a):ssa. Ei tarvinnut kertoa, miten oik. lin. kieliopista saa automaatin. c) Ongelma ei ratkea yleisessä tapauksessa laskennallisesti (vain jos kieliopit lineaarisia). Ainut keino matemaattinen todistus. - Jos kerrottu, miten ratkeaa lin. kielioppien tapauksessa, niin 0.5p - Jos kertoi, miten voi todistaa, että L(G1)!=L(G_2), niin 1p - Jos vain vertaillaan kielioppien rakenteita, niin 1.5p . Teht. 4 (W.H.) a)-kohdassa kumpikin jäsennyspuu max. 1.5 p, yht. 3p; b)-kohta max 3p,; c)-kohta max 4 p, yht. 10p. a) Ks. mallivastauspaperi. G2:lle saattoi antaa monelaisia jäsennyspuita, koska on moniselitteinen. - jos puuttuu vain kaaria, mutta muuten ok, niin 1.25p/puu - jos jäsennyspuusta puuttuvat lehtisolmut ja kaaria, mutta idea ok, niin 1p/puu - jos puuttuu sääntö E->(E) (puuttui monelta), niin -0.5p - jos terminaaleja sisäsolmuissa niin -0.5p - jos jäsennyspuun ideasta vain jokin aavistus, niin 0.5p/puu b) G2 on moniselitteinen, joten jäsennintä ei voi toteuttaa yksikäsitteisesti. Aritmeettisten lausekkeiden kohdalla erityisen ongelmallista, sillä ei noudata laskujärjestyssääntöjä (G1 noudattaa). Moniselitteisyyttä ei tarvinnut osoittaa. - Jos kertoo vain, että G1 yksisel. tai G2 monisel., mutta ei pohdittu, miksi ongelmallista, niin 2p. - jos idea ok (laskujärjestyssääntäjen evaluoinnissa tapahtuvat ongelmat), mutta ei mainittu moniselitteisyyttä, niin 2.5p. c) G1:n saa helposti LL(1)-muotoon, jolloin sille voi laatia rekursiivisen LL(1)-jäsentimen. Perusidea: luetaan merkkijonoa vasemmalta oikealle merkkikerrallaan ja sovelletaan kieliopin sääntöjä. Kun senhetkinen vlike ja syötemerkki tunnetaan, on sovellettava sääntö yksikäsitteiseti määrätty. Käytännössä laaditaan oma funktio kullekin välikkeelle. - Jos mainittu vain, että LL(1):stä saisi rekursiivisen jäsentimen, mutta ei mitään muuta, niin 1p