LATE 2. vk 11.5. 2007 Teht. 1, 10 pistettä (M.V.) a) 5p Kukin pääkohta 1p 1) lähtösymbolin poisto oikealta puolelta ei välttämätön, mutta jos tehty, niin yksikköproduktioissa huomioitava myös - "poistettu", mutta on edelleen oikealla puolella: 0p 2) tarkistetaan tyhjentyvyys (ei tyhjentyviä välikkeitä) - lisätty sääntöihin ylimääräinen epsilon, mutta käsitelty oikein: 0.5p 3) poistetaan yksikköproduktiot (E-->A ja mahd. E'-->E) - E'-->E jätetty: -0.5p - (A:n säännöt voidaan jättää pois) 4) luodaan päätemerkeille +, -, *, (, ) vastaavat välikkeet - lopputuloksessa päätemerkkejä säännöissä (muut kuin E-->a|b): 0p 5) pilkotaan ylipitkät produktiot b) 2.5p / merkkijono, yht. 5p - täytetään taulukko diagonaaleittain CYK-algoritmin mukaisesti - virheellisiä välikkeitä taulukossa: <= -0.25p/kohta - minimi 0.5p / merkkijono, kunhan täytetty koko taulukko ajatuksella Teht. 2, 10 pistettä (M.V.) Koneen periaate esim.: - etsitään ensimmäinen pieni 'a', muutetaan se isoksi ('A'), ja etsitään sille pariksi ensimmäinen pieni 'b', joka muutetaan isoksi ('B') - palataan merkkijonon alkuun - jatketaan ensimmäisestä kohdasta - jos nauhalla ei enää muuttamattomia merkkejä, syöte hyväksytään - jos a:lle ei löydy paria, tai nauhalla on 'b' muttei 'a':ta, niin hylätään - toimiva ajatus: 4p - toteutus: 6p - hylkäävän lopputilan piirtämistä ei vaadittu Teht. 3, 10 pistettä (W.H.) Kukin kohta max 2.5 p - oikea vastaus 1 p, täysin oikea perustelu 1.5 p - jos maininnut ratkeamattomaksi, mutta ei ottanut kantaa osittaiseen ratkeavuuteen, niin 1/2 p - jos osittaisen ratkeavuuden perustelusta vain toinen puoli (voidaan simuloida universaali TM:lla), niin perustelusta 1p. - jos a):ssa perusteluna tieto pysähtymisongelman osittaisesta ratkeavuudesta, niin täydet 1.5 p perustelusta - jos b):ssä ei kerro, että simulaation voi lopettaa |c_M| askeleen jälkeen, niin vain 1p perustelusta - jos c):n perusteluna viittaus pysähtymisongelmaan, mutta ei perusteltu tarkemmin, miksi palautuu siihen, niin 1 p perustelusta - jos d):ssä vain todettu, että kaikkia mahdollisia syötteitä yleisessä tapauksessa äärettömän monta, mutta ei huomannut, että ongelma on ratkeamaton jo yhdellä syötteellä, niin 1 p perustelusta. (Olisi edes pitänyt kertoa, että on semanttinen ominaisuus). Teht. 4, 8 pistettä (W.H.) - universaalikoneen idea 2 p * jos vain kerrottu, että niillä voi tutkia muiden koneiden toimintaa ja/tai niiden hyväksymiä syötteitä, niin 1.5 p - universaalikielen määritelmä (tai idea täsmällisesti, ts. sanat c_Mw missä w kuuluu M:n tunnistamaan kieleen) 2 p * jos kerrottu vain, että muotoa c_Mw, niin 1p - mitä merkitsee, että universaalikieli rekursiivisesti lueteltava, mutta ei rekursiivinen? * simulaatio ei välttämättä pysähdy (jos tutkittava kone ei pysähdy); universaalikone ei voi olla totaalinen 2 p * jos vain kertonut, ettei universaalikone voi olla totaalinen, niin 1 p * Turingin koneiden eli tietokoneohjelmien semanttiset ominaisuudet ovat ratkeamattomia 2 p * jos kerrottu, että universaalikonetta voi käyttää osoittamaan, että ongelma on osittain ratkeava, niin 1/2 p - jos kerrottu, että universaalikieleen on koodattu implisiittisesti tieto kaikesta, mitä TM:illä voi ratkaista, niin +1/2 p