KIT Ctl253, 2002k:
Äärellisten tilojen jäsennysmenetelmät

Muutoksia

Kurssi pidetään 21.1. alkaen Unix-luokassa.

Kurssin kulku

14.1.
Johdanto ja motivointi. Miksi
Millaisia deterministiset äärelliset automaatit ovat.
Säännölliset lausekkeet (RE, sellaisina kuin ne esim. Egrep-ohjelmalle on määritelty) vastaavat tarkoin deterministisiä äärellisiä automaatteja (FSA) sikäli, että voidaan mekaanisesti muodostaa jokaista säännöllistä lauseketta vastaava FSA, joka hyväksyy täsmälleen ne merkkijonot, jotka vastaavat RE:tä ja päinvastoin. Yleisemmät säännölliset lausekkeet, esim. Perlissä käytetyt, eivät vastaa äärellisiä automaatteja yhden ominaisuutensa vuoksi, eli niissä voidaan käyttää ilmausta /([a-z]+) \1/ ,joka tunnistaa kaksi peräkkäistä vaikka kuinka pitkää identtistä sanaa.
21.1.
Pyrittiin saamaan kaikki kurssilaiset BSCW-nimisen verkko-opetusjärjestelmän piiriin. Kullekin piti lähteä sähköpostin muodossa kutsu, jossa on yksityiskohtaiset ohjeet sisäänkirjottautumiselle. Kurssimme hakemistossa on tällä hetkellä kaksi keskusteluryhmää, joihin toivotaan kurssia koskevia repliikkejä. BSCW, jota käytämme, on laitoksellamme ylläpidetty oma palvelinkone, jota käytetään tässä vaiheessa vain KIT-verkoston tarpeisiin. Kukin opiskelija kutsutaan sähköposti-ilmoittautumisen perusteella palvelimella oleville kursseille. Kutsu tulee sähköpostitse ja siinä on tarkka ohje, jota tulee noudattaa. BSCW toimii riittävän hyvin Netscapella ja Explorerilla, mutta ei esim. Konquerorilla. Jos kutsun saannin jälkeen on ongelmia ilmottautumisessa, (lukekaa ensin saamanne ilmoittautumisohjeet vielä kerran, ja raportoikaa sitten ongelmasta sähköpostitse luennoitsijalle.

Kokeiltiin van Noordin FSA -ohjelmaa ja ratkottiin sen avulla muutamia pieniä ongelmia:

  1. Automaatti, joka hyväksyy ne ja vain ne merkkijonot, jotka koostuvat parittomasta määrästä 'x'-kirjaimia. Van Noordin merkintätavan mukaan tämä vastaa lauseketta [x,[x,x]*] . Siis yksi x, jonka perässä on nolla, yksi tai useampia kahdesta x:stä koostuvia jonoja.
  2. Automaatti, joka hyväksyy ne ja vain ne merkkijonot, joissa on ensin 'a'-kirjaimia ja sitten 'b'-kirjaimia ja niitä on keskenään yhtä monta kappaletta, kuitenkin enintään 5. Van Noordin merkintätavan mukaan tämä on words([ab, aabb, aaabbb, aaaabbbb, aaaaabbbbb]) , missä on suoraan lueteltu kieleen kuuluvat merkkijonot. words() -funktion avulla meidän ei tarvitse kirjoittaa jokaista merkkijonoa hakasulkulausekkeeksi, esim. [a,b] .
  3. Automaatti, joka hyväksyy parin sanan, esim. 'talo' ja 'solu' muutamia taivutusmuotoja kuten päätteet 'n', 'a', 'ssa' ja 'sta'.

Fsa-ohjelman avustuksesta (HELP) saa lisää tietoa eri funktioita ja operaattoreista. Avustusta on syytä selata sen verran, että löytää tarvittaessa tärkeimmät konstruktiot.

28.1.
Äärellisten automaattien teoriasta keskeisiä osia. Deterministinen äärellinen automaatti eli DFSA voidaan tunnistaa siitä, että siinä on (1) tasan yksi alkutila, (2) kaikki siirtymät koostuvat yhdestä merkistä ja (3) mistään tilasta ei ole kahta eri siirtymää samalla merkillä.
Vastaavasti epädeterministinen äärellinen automaatti eli NFFSA poikkeaa jossakin yllä mainituista suhteista, eli (1) siinä voi olla enemmän kuin yksi alkutila, (2) siinä saattaa olla siirtymiä, joiden nimiönä on yhtä merkkiä lyhyempi tai pitempi merkkijono ja/tai (3) siinä on joistakin tiloista samalla merkillä useampia erilaisia siirtymiä. Nollan mittainen siirtymä on ns. epsilon-siirtymä, joka ei kuluta tunnistettavasta merkkijonosta yhtään merkkiä. Epsilon-siirtymän voi siten joko toteuttaa tai jättää toteuttamatta.
Epädeterministiselle automaatille on ominaista se, että ainakin joidenkin merkkijonojen tunnistamisen jälkeen ne voisivat olla kahdessa tai useammassa tilassa. Epädeterministisen automaatin sanotaan tunnistavan merkkijonon, jos löytyy yksikin tilasiirtymien reitti, mitä myöten tunnistus onnistuisi.
Determinisointi tarkoittaa sitä, että epädeterministiselle äärelliselle automaatille muodostetaan ekvivalentti DFSA. Ekvivalentti tarkoittaa sitä, että uusi automaatti hyväksyy täsmälleen samat merkkijonot kuin alkuperäinen. Determinisointi voidaan tehdä siten, että muodostetaan uusi automaatti, jonka tiloina ovat alkuperäisen automaatin tilojen osajoukot , joita on 2**n, jos alkuperäisessä automaatissa on n tilaa. Tiloja on siis tämä määrä ja kunkin uuden tilan nimenä käytämme sitä vastaavaa vanhan automaatin tilojen osajoukkoa. Uuden automaatin alkutila on se osajoukko tiloista, joissa alkuperäinen automaatti voi olla alussa, siis kaikki alkutilat ynnä tilat, joihin niistä voi siirtyä epsilon-siirtymällä. Lopputiloiksi merkitään ne tilat, joita vastaavaan tilajoukkoon sisältyy ainakin yksi alkuperäisen automaatin lopputila. Siirtymät lasketaan siten, että uuden automaatin kutakin tilaa vastaavasta alkuperäisen automaatin tilajoukosta katsotaan, mihin tiloihin alkuperäisessä automaatissa voitaisiin kullakin merkillä päästä. Automaatista voidaan sitten karsimalla pois kaikki ne tilat, joihin ei millään siitymällä voi päästä alkutilasta käsin.
Käytännössä 2**n voi muodostua piankin liian suureksi. Sen vuoksi kannattaa muodostaa ensin alkutila kuten yllä. Sitten siitä ja samalla tavoin kaikista tässä prosessissa syntyvistä uusista tiloista kehitetään siirtymät. Jos siirtymien maalina olevat tilat ovat jo valmiina, kytketään siirtymä tietenkin sinne, muutoin konstruoidaan tarvittava uusi tila. Prosessi pysähtyy, kun uusia tiloja ei enää synny, ja kaikki tähänastiset tilat on käsitelty.
Epsilon-siirtymien avulla voidaan melko helposti konstruoida olemassa olevista automaateista uusia. Esim. toisto voidaan tehdä siten, että lisätään uusi tila alkutilaksi ja siitä epsilon-siirtymä entiseen alkutilaan ja vielä kustakin lopputilasta epsilon-siirtymä tähän uuteen alkutilaan. Jos halutaan Kleenen tähteä (*) vastaava toisto, merkitään uusi alkutila lopputilaksi, jos Kleenen plussaa (+) vastaava toisto, ei alkutilaa merkitä loputilaksi. Tällaisia konstruktioita tehdessä on oltava hieman varuillaan, koska esim. säännöllistä lauseketta "b*a" vastaavassa automaatissa ei voida oikaista merkitsemällä alkuperäistä alkutilaa lopputilaksi, jos tehdään *-toistoa, sillä tällainen automaatti hyväksyisi väriäkin merkkijonoja, mm. jonon "b".
Vastaavasti yhdiste eli unioni muodostetaan lisäämällä yksi uusi alkutila ja siitä epsilonsiirtymät alkuperäisten automaattien alkutiloihin. Lopputilat säilyvät ennallaan.
Peräkkäinasettaminen eli konkatenaatio tehdään analogisesti siten, että ensimmäisen automaatin lopputiloista laitetaan epsilonsiirtymät jälkimmäisen automaatin alkutilaan, jonka jälkeen alkutilana toimii vain ensimmäisen automaatin alkutila ja ensimmäisen automaatin lopputilat merkitään ei-lopputloiksi. Jälkimmäisen automaatin lopputilat toimivat konkatenoidun automaatin lopputiloina.
4.2.
Xeroxin äärellisten automaattien työkaluihin perehtymistä. Laitoksen Linux-palvelimilla on Finite-State Morphology: Xerox Tools and Techniques -nimisen kirjan (ei-lopullisen version) käsikirjoitus hakemistossa /ling/courses/ctl253/2002k/. Se on PostScritiä ja sitä voi selata ghostview -nimisellä ohjelmalla. Itse ohjelmat (xfst, twolc, lexc ja lookup) ovat Donnerilla (ei siis enää Ahtelalla). Kirjan lisäksi kyseisten ohjelmien manuaalit löytyvät XRCE:n sivuilta.
11.2.
Xeroxin finite-state-työkalujen käyttöä esimerkkien valossa. Kurssin hakemistossa /edu/courses/ctl253/2002k/ on muutamia kokonaisia esimerkkejä. Sovittiin alustavasti useista loppu- eli harjoitustöiden ahieista.
18.2.
Keskusteltiin harjoitustöiden aiheista ja tekemisestä.
25.2.
Sovittiin harjoitustyön palauttamisen aikataulu ja, että lopuksi pidetään vielä yksi yhteinen istunto, jossa hrjoitustyöt esitellään ja kommentoindaan. Päivämäärät harojitustyötä kuvailevassa kohdassa.
Harjoitustöiden ohjaus jatkuu BSCW-järjestelmän puolella.

Käsitteitä

Taitoja

Materiaali

Kysymyksiä ja vastauksia
Kurssin aikana ilmaantuneita kysymyksiä ja vastauksia, erityisesti harjoitustyön tekemiseen liittyviä.
Linkkisivu
GRAIL-hankkeen ylläpitämä lista äärellisten automaattien käsittelyohjelmista. Luettelo on varsin täydellinen ja sen kautta kannattaa etsiä (joskaan kaikki linkit eivät enää ole ajan tasalla).
FSA utilities
Gertjan van Noordin FSA -ohjelma on Prolog-kielellä laadittu äärellisten automaattien manipulointiohjelma, joka toimii Donnerilla ja Ahtelalla. Sillä voidaan mm. modostaa säännöllisestä lausekkeesta äärellinen automaatti, saada automaatti graagisesti näkyville ruudulle ja tulostetuksi esim. PostScriptina. Ohjelma käynnistyy komennolla fsa -tk ja siitä saa ohjeita napsauttamalla yläpalkissa olevaa "Help"-nappulaa. Ohjelmaa voi käyttää mm. siten, että Regex-kohtaan kirjoittaa säännöllisen lausekkeen, joka Enterin painamisen jälkeen muunnetaan äärelliseksi automaatiksi, joka visualisoidaan saman tien. Automaatin graafista esitystä voi korjailla siirtämällä tiloja hiiren avulla. Ohjelman rakentaman automaatin voi tulostaa erinäisiin eri muotoihin mukaan lukien ohjelmakoodin pätkäksi, jonka voi liittää omaan ohjelmaansa. Erityisen mukava piirre on se, että ohjelma on ns. avointa koodia eli GNU-lisenssin mukainen. Van Noordin ja Xeroxin käyttämistä säännnöllisten lausekkeiden merkintätavoista on koostetaulukko, jota vastaavuudet näkyvät.
Xeroxin finite-state -työkalut
Ne toimivat vain Donnerilla ja voidaan käynnistää komennoilla: xfst, lexc, lookup ja twolc. Ohjeita bscw järjestelmän takana. Ilmoittautukaa sähköpostitse saamienne ohjeiden mukaisesti. Ottakaa yhteys luennoitsijaan, jos on ongelmia.

Harjoitustehtävät

Tehtävä 1
Käytä xfst -ohjelmaa laatiaksesi säännölliset lausekkeet seuraavia (formaaleja) kieliä varten ja käännä ne automaateiksi: (a) parillinen määrä 'x'-kirjaimia, siis {"", "xx", "xxxx", ...}, (b) avotavuiset sanat, jossa "a" saa edustaa kaikkia vokaaleja ja "t" kaikkia konsonantteja, (c) sama kuin edellä, mutta kaikkien suomen kielen aakkosten kanssa.
Laadi kahdesta ensimmäisestä kohdasta kynällä automaatti ja kokeile kahdella valaisevalla esimerkkimerkkijonolla. Merkitse, mitten tilojen kautta merkkijonot tulivat hyväksytyiksi.
Vinkkejä: xfst:n regex -komennolla saa annetun lausekkeen muodostetuksi automaatiksi, joka tulee pinon päällimmäiseksi. Komennolla net saa tulostetuksi syntynee automaatin (eli tilasiirtymäverkon). Muista, että Xeroxin formalismissa hakasulut toimivat ryhmittelevinä sulkuina ja pyöreät sulut on varattu valinnaisuuden osoittamiseen. Merkkien väliin pitää jättää tyhjää. Kohdassa c on syytä määritellä define -komennolla vokaalit ja konsonantit nimellä varustetuiksi lausekkeiksi, joita varsinaisessa lausekkeessa käytetään.
Tehtävä 2
Beesleyn ja Karttusen kirjassa (Finite State Morphology: Xerox Tools and Techniques, luonnos, 2002) on sivulla 481 (elektronisessa PostScript-versiossa) joukko äärellisten automaattien piirtotehtäviä "Graphing Quiz". Kirjassa on myös vastaukset valmiiksi piirrettynä, mutta älä katso niitä, ennen kuin olet mielestäsi vakuuttunut oikeasta ratkaisusta ja vaikka tarkistanut ehdotuksesi xfst -ohjelmalla. (Sitten voit katsoa graafinkin).
Tee seuraavat osiot, ellet ole aivan varma, että tiedät oikean vastauksen. (Ellet ole varma osaamisesta, tee kuitenkin.)
Älä hosu, vaan mieti kunnolla määritelmistä lähtien (PostScript-kirjan ss. 41-47 ), mitä tuloksena pitäisi olla. Jos päädyt eri tulokseen, kuin mitä xfst antaa, tarkista määritelmäsi.

Harjoitus- eli loppytyön suorittaminen ja sen aiheita

Sovi ensin alustavasti lopputyösi aihe luennoitsijan kanssa. Tee lopputystäsi ensin lyhyt, esim. 10 rivin mittainen suunnitelma, joka käydään läpi luennoitsijan kanssa. Työn tuloksena on (1) HTML-dokumentti, joka kertoo lyhyesti, mitä on tehty, (2) säännöstö tms. lähdekielinen ainesto, joka toteuttaa suunnitelman, (3) testiaineisto ja tulokset testistä. Dokumentissa on hyvä arvioida, paljonko (koko laajemmasta) tehtävästä tuli tehdyksi ja kuinka hyvin onnistuttiin.

Harjoitustyö on palautettava viimeistään 8.4.2002 laittamalla tarvittavat (yllä mainitut) dokumentit BSCW:hen HTML- ja/tai pelkkää tekstiä sisältävinä dokumentteina ("upload" eli "add document").

Suunnittelun alkuvaiheessa on syytä laatia esimerkki esitysmuotojen kera siitä, mitä tarkoitus on tehdä. Esimerkiksi suomen kielen morfologisen analysaattorin tehtävän voi aika tarkasti luonnehtia esimerkillä, jossa on (a) hakusana ynnä piirteet, (b) morfofoneeminen esitysmuoto ja (c) pintamuoto:

          k a u p  p  a +N +PL +INE
          k a u p ^P ^a2   ^I   s   s ^A
          k a u p  0  o     i   s   s  a

Esimerkiksi tavutussäännöstöä laadittaessa vastaava testitiedosto voisi olla tiedosto, jossa on toisaalta tavanomaisia sananmuotoja ja toisaalta tavutuksen kannalta ongelmallisempia sananmuotoja varustettuna tavujakokohtien merkeillä (esim. alaviivoilla). Suomen kielen tapauksessa testitiedosto voisi näyttää seuraavalta:

ta_los_sa
kau_an
tie_aloi_te
kan_san_edus_ta_ji_aan
pää_omas_ta

Jos tavutus koostuu useammista vaiheista, on näiden lisäksi useinkin tarpeen tehdä toisenlainenkin tiedosto, eräänlainen esimerkkitiedosto, jossa kuvataan sanamuodon käsittelyn eri vaiheita, esim.:

kansanedustajille
kansan_edustajiaan     ! sääntöjenvastaisten yhdyssanojen käsittelyn jälkeen
kansan_edustaji_aan    ! varmojen vokaalisekvenssien käsittelyn jälkeen
kan_san_edus_ta_ji_aan ! CV-säännön jälkeen

Tällaiset nimettävissä olevat välivaiheet ovat tarpeen, jos säännöillä on keskenäisiä interaktioita.

Kelpuutetut ja käynnistyneet harjoitustyöiden aiheet näkyvät kurssin BSCW-sivuilla.

Mahdollisia muita aiheita:

Kurssin suoritus

Kurssi suoritetaan tekemällä kullekin opiskelijalle tai ryhmälle erikseen sovittava lopputyö.


KIT-logo
Viimeksi päivitetty: Monday, 20-May-2002 13:17:46 EEST