Yliopiston etusivulle Suomeksi
Helsingin yliopisto
clt270: Äärellistilaiset jäsennysmenetelmät - syksy 2005

Yhteystiedot

Yleisen kielitieteen laitos
PL 9 (Siltavuorenpenger 20 A)
00014 Helsingin yliopisto

Puhelinvaihde +358 (09) 1911
Faksi +358 (09) 191 29307

CLT270: Äärellistilaiset jäsennysmenetelmät: Kurssin ydinainekset

Ydinainesten luetteloa voi käyttää eräänlaisena tarkistuslistana kurssin suorituksen aikana. Jos alla on käsitteitä tai taitoja, jotka tuntuvat vierailta, on syytä mennä viikottaisiin kurssimateriaaleihin ja tarkistaa sieltä vieraaksi jääneet kohdat.

Äärellistilaiset automaatit Xeroxin formalismissa

Säännölliset lausekkeet ym.

  • merkki; merkkijono; tyhjä merkkijono (epsilon); monimerkkinen symboli; mikä tahansa yksi merkki (?);
  • formaali kieli (merkkijonojen joukko); tyhjä kieli (tyhjä joukko);
  • säännöllinen lauseke; peräkkäinasettelu; vaihtoehto (|); kleenen tähti (*); kleenen plus (+); valinnaisuus (()); ryhmittely ([]);

Äärellinen automaatti

  • äärellinen automaatti ja miten se toimii; tila; alkutila; lopputila; (tila)siirtymä; äärellinen automaatti hyväksyy tai hylkää merkkijonoja;
  • yksinkertaisten äärellisten automaattien konstruoiminen käsin;
  • äärellisen automaatin piirtäminen esim. FINOMATON -ohjelmalla;
  • kyky tulkita XFST:n tuottama yksinkertainen automaatti graafisina tiloina ja siirtyminä;
  • deterministinen automaatti; epädeterministinen automaatti; epsilonsiirtymä;

Äärellinen transduktori

  • merkkipari; oletussääntö (a on sama kuin a:a); toinen parissa voi olla epsilon eli tyhjä merkkijono; merkkiparien jono vastaa kahden merkkijonon paria (esim. k:c i:a s:t s:epsilon a:epsilon vastaa merkkijonojen "kissa" ja "cat" paria)
  • säännöllinen relaatio (merkkijonoparien joukko); säännöllisten relaatioiden formalismi muutoin sama kuin säännöllisten lausekkeiden (saa olla merkkipareja, yksittäiset merkit tulkitaan merkkipareiksi);
  • äärellinen transduktori ja sen toiminta:
    • lukee yhtä merkkijonoa ja tulostaa toista (tai vertaa kahta merkkijonoa tai sitten tunnistaa merkkiparien jonoja)
    • merkkijonot voivat olla eri pituisia
    • muuntamisen lisäksi transduktori voi hyväksyä tai hylätä

LEXC:n leksikkoformalismi

  • leksikkojärjestelmä koostuu osaleksikoista (LEXICON) ja niissä olevista morfeemien tms. kuvauksista (entryistä);
  • kuhunkin entryyn liittyy kolme asiaa:
    • ylempi merkkijono (perusmuoto ja piirteitä)
    • alempi merkkijono (morfofoneeminen esitysmuoto tai kirjoitettu asu)
    • jatkoleksikon nimi (tai lupa lopettaa, #)
  • transduktorit yleistetään usein sellaisiksi, että siirtymässä voi olla merkkiparin sijasta mielivaltaiset kaksi merkkijonoa (sillä tällainen voidaan mekaanisesti muuntaa merkkipareilla toimivaksi transduktoriksi);
  • leksikkojärjestelmä voidaan suoraan tulkita tällaisena yleistettynä transduktorina:
    • jokainen osaleksikko on tila, jonka nimenä on leksikon nimi; alkutilana ensimmäinen leksikko; lopputilana #;
    • entryt siirtymiä siitä tilasta, jota vastaavassa leksikossa ne ovat, jatkon nimeä vastaavaan tilaan entryssä olevalla kahden merkkijonon parilla
  • tehdyn leksikkojärjestelmän kääntäminen transduktoriksi ja kokeilu LEXC:n avulla (lookup, lookdown, check-all);
  • taito tehdä yksinkertaisia kiinteistä sanoista tai muutamalla päätteellä varustetuista sanoista LEXC-kuvaus, joka tunnistaa nämä (toistaiseksi ilman sääntökomponenttia);

XFST:n toisinkirjoitusformalismi

  • käynnistäminen; pino ja sen tyhjentäminen (clear stack); ohjelman lopettaminen (quit);
  • säännöllisen lausekkeen nimeäminen (define); säännöllisen lausekkeen syöttäminen pinoon (read regex);
  • tilasiirtymäverkon tulostaminen (print net);
  • toisinkirjoitussäännöt: A -> B; [A -> B || L _ R];
  • rinnakkaiset toisinkirjoitussäännöt: [A -> B, C -> D];
  • peräkkäiset toisinkirjoitussäännöt: [A -> B] .o. [C -> D];
  • pisimmän merkkijonon toisinkirjoitus: A @-> B
  • tyhjän merkkijonon toisinkirjoitus kertaalleen: [..] -> L _ R;
  • tehdyn transduktorin (säännöstön) kokeilu (apply down, apply up);
  • taito tehdä yksinkertaisia toisinkirjoitukseen perustuvia säännöstöjä;
  • miten poikkeus ja yleisempi sääntö yhdistetään toisinkirjoitusformalismilla (poikkeus ensin ja yleisempi sitten);