Maht: 64 tundi auditoorset tööd (32 t. loenguid, 32 t. praktikume), 56 t. iseseisvat tööd

1 semester, 4 tundi nädalas

3 ainepunkti

Eeldusained: Matemaatika arvutuslingvistidele I

Sisu lühikirjeldus: tutvustatakse lingvistikas vajalikku matemaatilist aparatuuri: algebrat ning formaalsete keelte ja automaatide teooriat.

Kohustuslik kirjandus:
1. B.H. Partee, A. ter Meulen, R.E.Wall. Mathematical Methods in Linguistics. Kluwer, 1990.

 Vt. ka
http://www.ifi.unizh.ch/CL/schacht/index.html Mathematische Grundlagen der Computerlinguistik
http://www.coli.uni-sb.de/~saurer/lehre/ws00/mg1-ws00.html Mathematische Grundlagen der Computerlinguistik I: Mengenlehre, Algebra und Logik
http://www.coli.uni-sb.de/~saurer/lehre/ss00/mg2/mg2-ss00.html Mathematische Grundlagen der Computerlinguistik II: Formale Sprachen und Automaten
F.D.Lewis. Essentials of Theoretical Computer Science

Programm

l - loeng, p - praktikum, i - iseseisev töö

I. ALGEBRA. [1], lk. 249-316.

1. Algebra põhimõisted. Algebra mõiste. Operatsioonide omadused. Kujutused ja morfismid. (2 l, 2 p, 4 i)
2. Operatsioonilised struktuurid. Rühmad. Alamrühmad, poolrühmad, monoidid. (2 l, 2 p, 4 i)
3. Võred. Osaliselt järjestatud hulgad, duaalsus ja diagrammid. Võred, poolvõred ja alamvõred. Morfismid võredes. Filtrid ja ideaalid. (4 l, 4 p, 7 i)
4. Boole'i ja Heytingi algebrad. Boole'i algebra. Boole'i algebra mudelid. Esitus hulkade abil. Heytingi algebra. Kripke semantika. (4 l, 4 p, 7 i)

1. Põhimõisted. Grammatika, keel, automaat. Chomsky hierarhia. Puud. (2 l, 2 p, 4 i)
2. Lõplikud automaadid, regulaarsed keeled ja regulaarsed grammatikad. Lõplikud automaadid. Regulaarsed grammatikad. Regulaarsed keeled. Nende omadused. (2 l, 2 p, 4 i)
3. Magasinmäluga automaadid, kontekstivabad keeled ja kontekstivabad grammatikad. Magasinmäluga automaadid. Kontekstivabad grammatikad. Kontekstivabad keeled. Nende omadused. (4 l, 4 p, 7 i)
4. Turingi masinad, rekursiivselt loetletavad keeled ja 0-tüüpi grammatikad. Turingi masinad. Churhi hüpotees. Rekursiivsed ja rekursiivselt loetletavad hulgad. Turingi masina peatumise probleem. (2 l, 2 p, 4 i)
5. Lineaarselt tõkestatud automaadid, kontekstitundlikud keeled ja kontekstitundlikud grammatikad. Lineaarselt tõkestatud automaadid. Kontekstitundlikud grammatikad. Kontekstitundlikud keeled ja rekursiivsed hulgad. Nende omadused. (4 l, 4 p, 7 i)
6. Pehmelt kontekstitundlikud keeled ja grammatikad. Indekseeritud grammatikad. Puuühendamisgrammatikad. Peajuhitavad grammatikad. Kategoriaalsed grammatikad. Nende grammatikatega genereeritavad keeled. (4 l, 4 p, 4 i)
7. Transformatsioonigrammatikad. (2 l, 2 p, 4 i)

Loeng E 14-16, praktikum N 12-14 Liivi 2-315

Kordamisküsimused

Eksam 1) neljapäeval, 29. mail kell 12.15-14 Liivi 2-315, 2) esmaspäeval, 2. juunil kell 14.15-16 Liivi 2-315. Eksam on kirjalik, 10 küsimust ja/või ülesannet.