Korjaus-/täydennyslista luentomateriaaliin

Liukulukuautomaatti: korjaus

Äärelliset automaatit, liukulukuautomaatin siirtymäkaavio (H:n luentomonisteessa esim. 4.1): myös q3 on hyväksyvä lopputila (kuten siirtymätaulukossa), samoin q1, jos hyväksymme myös kokonaisluvut -> lisää toinen ympyrä. Alkutila q0 on hyvä merkitä nuolella.

Automaatti ei kuitenkaan hyväksy C:n mukaisia liukulukuja, vaan Pascalin mukaiset (esimerkki on perua vanhasta monisteesta, jossa kaikki oli Pascalilla, ja jäänyt korjaamatta). C:n mukaiset liukuluvut ovat hieman monimutkaisempia (ks. Kerninghan & Richie, A2.5.3):

Liukuluvun esitys sisältää kokonaislukuosan, desimaalipisteen, desimaaliosan, e- tai E-kirjaimen, mahdollisesti etumerkillisen eksponentin ja mahdollisesti tyyppimerkin (f, F, l tai L). Kokonaisluku- ja desimaaliosa koostuvat molemmat lukumerkeistä. Jompikumpi (mutta ei molemmat) saa puuttua. Joko desimaalipiste tai e ja eksponentti saa puuttua, mutta eivät molemmat. Tyyppimerkki kertoo, onko kyseessä float (F, f) vai long double (l, L); muuten kyseessä on double. Tämän mukaan liukulukuja ovat myös merkkijonot, joissa on lukumerkkejä ja lopussa piste (esim. "1.").

Vastaava säännöllinen lauseke on annettu esimerkissä 4.10. Otetaan esimerkki, jossa se muunnetaan automaatiksi!

O:n uudessa monisteessa (vuodelta 2003), kuva 2.3, kaavio on oikein kaikkine erikoistapauksineen (mutta ei minimaalinen).

Oikeellinen automaatti löytyy myös tästä esimerkistä.

Kokonaislukuautomaatti: täydennys

Kokonaislukuautomaatti (H:n monisteessa esim. 4.2) Huom! Jos haluat kieltää nollalla alkavat kokonaisluvut, täytyy siirtymissä q0-q2 ja q1-q2 kieltää merkki "0". Lisäksi on tehtävä oma siirtymä uuteen lopputilaan q3, jotta voimme hyväksyä merkkijonon "0": delta(q0,0)=q3.

O:n uudessa monisteessa (kuva 2.5) ongelma on kierretty tunnistamalla oktaali- eli 8-kantalukuja, jotka saavat alkaa "0":lla. Tämä selviää vain tekstistä. Huom! Oktaaliluvuissa ei saa esiintyä merkkejä 8 ja 9 eli se pitäisi tutkia erikseen.

MIU-automaatin determinisointi: korjaus

MIU-kielen tunnistusautomaatissa (luentomonisteen esimerkki 4.7, myös luentokalvoissa) taulukon rivillä F lukee

F {0,2} {0,3}=E {0}=A {0,3}=G

Pitää olla:

F {0,2} {0,1}=E {0}=A {0,3}=G

Esimerkki 4.14: säännöllisestä lausekkeesta automaatti

Esimerkissä 4.14 (s. 74) on determinisoinnissa virhe: C:n seuraajatilajoukko merkillä a ei sisällä tilaa 4. Täytyy siis luoda uusi tila E. Tällöin deterministisestä automaatista ja vastaavasti minimoidusta automaatista tulee erilainen. Korjattu sivu löytyy täältä.

4.9 Säännöllisten kielten harjoitustehtävissä esiintyviä (tahattomia) kompia

5.9.2 Aritmeettinen laskin

Funktion F koodissa oli yksi ylimääräinen next=getnext, säännön F->(E) jäsennyksessä. Korjattu sivu 163.

5.13 Kontekstittomien harjoitustehtävissä esiintyviä (tahattomia) kompia

Esimerkki 6.1

Ohjelmakoodi ei vastaa annettua kieltä (eikä Turingin konetta), sillä se tutkii vain, että merkkijonossa on yhtä monta a:ta, b:tä ja c:tä. Kielessä edellytettiin merkeiltä lisäksi järjestystä: a^nb^nc^n.

7.4 TM:ien kooditaulu

Loppu- ja alkumerkit määriteltiin tekstissä numeroiksi a2 ja a3 (> = 000 ja < = 0000) eli ensimmäinen muu aakkonen on a4=00000. Kooditaulussa aakkosten ideksit ovat väärin. Jos syöteaakkosto on {0,1}, voi silti olla tällaisia apuna käytettäviä nauhamerkkejä. (Huom! Alku- ja loppumerkki eivät ole koneen aakkosia eli jos tarvitset syöteaakkostossa merkkejä > ja <, niin pitää määritellä jotkin muut erikoismerkit alku- ja loppumerkeiksi.)

7.7.5 Busy Beaver-kuva

Kuvan 3-tilainen Turingin kone, jonka pitäisi kirjoittaa 6 1:ä, ei toimi. Alkuperäinen kone ei nimittäin ollut kurssin standardimallia, vaan työnauha oli kumpaankin suuntaan ääretön. Tällöin kone toimii, kun korvaat nauhan loppumerkin < yleisellä tyhjämerkillä (joka voi olla nauhan vasemmassa tai oikeassa päässä). Lisätietoa