Logik och matematisk lingvistik 7,5hp (AC1203)


Kurshemsida höstterminen 2007
(Uppdaterad 2007-12-17)

Lärare är Martin Kaså Palmé och kursen ges av logikavdelningenFilosofiska institutionen inom ramen för Språkteknologiprogrammet.

Kursen startar vecka 45 och undervisningen äger rum på tisdagar och torsdagar kl 13-16 i sal S214 på Dicksonsgatan 12.

Inställd föreläsning torsdag 22 nov  pga sjukt barn.

Extra föreläsning måndag 3 december kl 9-12.

>> Övningstenta (pdf) <<

>> Hemuppgift 1 (pdf) Inlämnas senast 20/11 <<

>> Hemuppgift 2 (pdf) Inlämnas senast  4/12 <<

>> Hemuppgift 3 (pdf) Inlämnas senast 11/12 <<

>> Hemuppgift 4 (pdf) Inlämnas senast 8/1 <<

>> Guide till regel T (pdf) <<

Preliminär plan för föreläsningarna

1. Introduktion: logik och automatateori inom språkteknologin. Formella grammatiker, formella språk, automater, logisk form.
Text: Bennet kap 1 + Beesley&Karttunen Preliminaries, 1.1-1.5 (+ Westerståhl)

2. Mängdteoretisk elementa. Vokabulär, abstraktion, extensionalitet, mängdoperationer, begreppen relation och funktion.
Text: Bennet kap 10.1-10.4

3. Mera mängder. Kardinalitet mm. En matematisk (axiomatisk) teori  om mängder.
Text: Bennet kap 10

4. Inledning till Första ordningens logik. Syntax, grundbegrepp och satslogiska metoder.
Text: Bennet kap 2, 3.2, 6.2

5. Logisk form. Basal formalisering.
Text: Bennet kap 3

6. Logisk analys av naturligt språk. Mer formalisering.
Text: Bennet kap 3 + Westerståhl

7. Formaliserade bevis i FOL. Naturlig deduktion I
Text: Bennet kap 6

8. Naturlig deduktion II
Text: Bennet kap 6

9. Formella språk. Grammatiker och abstrakta maskiner. Chomskyhierarkin
Text: Altenkirch kap 1 och 2 och/eller Forsberg s 4-8, 10-11
(eventuellt Wikipedia: Automata theory)

10. Reguljära uttryck. Att kompilera: regex>>NFA>>DFA. Reguljära relationer och transduktorer.
Text: Altenkirch kap 2.2.3, 3 och/eller Forsberg s  8-10, 11-15, 17-19 + Beesley&Karttunen kap 1 (igen)

11. xfst
Text: Beesley&Karttunen kap 2 och 3.1-3.3

12. Bortom det reguljära. Pumpning, kontextfria språk, PDA och Chomskyhierarkin (igen)
Text: Altenkirch kap 4 samt 5 och 6 (översiktligt)
(eventuellt Wikipedia: CFG)

13. Repetition, framåtblick, fågestund
Text: Övningstenta + vad ni vill

Böcker och annat kursmaterial

[1]  Bennet, Christian: Första ordningens logik (ISBN 9144034539)

(Mer av denna bok används på kursen Logik, sannolikhetslära och statistik)

[2] Beesley&Karttunen: Finite State Morphology (ISBN 1575864347)

(Mer av denna bok används på kursen Komputationell lexikologi och morfologi)

Se även bokens webbplats samt Xerox.

[3] Westerståhl, Dag: "Mening och logik" (stencilerad ur Filosofisk tidskrift 1994)

[4] Altenkirch, Thorsten: Machines and their languages -- Lecture notes

        "for online viewing"
        "for printing"

[5] Forsberg, Markus: Finite State Transducers in Haskell

        Postscript    pdf

[7] The Finite State Machine Explorer (Matt Chapman)

[8] Visual Automata Simulator (Jean Bovet)

[9] En mycket simpel DFA-simulator: fsm.jar (länk kommer snart)

[10] Med viss försiktighet: wikipedia.org

Utöver detta tillkommer övnings-/labbuppgifter och övningstentor.

Kursplan
Den formella kursplanen för AC1203 hittar du här (pdf).

Examination
* obligatoriska hemuppgifter/labbuppgifter (ej graderade)
* skriftlig tentamen (betygsgradering U/G/VG)