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
- Teht. 11: automaatista puuttuvat aakkoset.
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
- 2c) ei ole kontekstiton kieli! Pitäisi olla wv, missä
w=a_0a_1...a_n ja v on saatu a_n a_(n-1)...a_0:sta vaihtamalla kaikki
a:t b:ksi ja päinvastoin.
- teht. 21 kielioppia ei saa LL(1):een (on LL(2)), ellemme muuta U:n
sääntöä muotoon U->Uu|u (oltava siis ainakin yksi u).
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