Matematisk Lingvistik VT97

This is an overview of the course Formal Languages and Automata (in Swedish: Matematisk Lingvistik) that will been taught in the Winter term of 1997 at the Department of Linguistics at Uppsala University. There is a page for this course on World Wide Web at the address:

The course will be given by Erik Tjong Kim Sang. I can be reached in room B382, HSC building, Kyrkogårdgatan 10, Uppsala, telephone (018) 181175, e-mail

You can take a look at summaries of the results of the midcourse evaluation and the final evaluation.


The schedule mentions date, time and location of the lectures. All lectures will be given in the HSC building. The subject in each lecture has been indicated by section numbers from the course book by Partee and others. Behind the sections you can find optional exercises from this book which you can make to test your comprehension of the lecture material.

       date time  room  subject
 1. on 0204 12-15 A128  Lecture: Ch 1.1-1.7. Ex 1.1, 1.5, 1.7, 1.9.
 2. to 0304 12-15 F324  Lecture: Ch 1.8-2.4. Ex 2.1, 2.3.
 3. må 0704 14-16 H339  Exercise class 1
 4. on 0904 12-15 B135  Lecture: Ch 3.1-3.4. Ex 3.1, 3.3.
 5. to 1004 12-15 H339  Lecture: Ch 3.5.     Ex 3.5.
 6. må 1404 14-16 A128  Exercise class 2
 7. on 1604 12-15 B135  Lecture: Ch 16.1-16.3.
 8. to 1704 12-15 H433  Lecture: Ch 16.4-16.6.
 9. må 2104 14-16 A128  Exercise class 3
10. on 2304 14-17 H433  Lecture: Ch 17.1-17.2. Ex 17.1, 17.3, 17.10.
11. to 2404 12-15 H433  Lecture: Ch 17.3. Ex 17.11, 17.12.
12. må 2804 14-16 A128  Exercise class 4
13. må 0505 14-16 H339  Lecture: Ch 18.1-18.3. Ex 18.1.
14. on 0705 13-16 B135  Lecture. Ch 18.4-18.6. Ex 18.5, 18.6.
15. må 1205 14-16 H339  Exercise class 5
16. on 1405 14-17 B135  Lecture: Ch 19.1-19.5
17. to 1505 12-15 H433  Lecture: Ch 19.6-19.7. Ex 19.1, 19.3.
18. to 2205 12-15 H433  Exercise class 6
    on 0406 14-18 Pola  Test 
    fr 2706 09-13 A118  Extra test (HSC building)

There are no obligatory sessions. However the students are advised to visit the exercise classes because the assignments they will receive during those sessions partially determine their grade.

There is a practice test with answers available. The file is in postscript format If you have problems printing the file you may consider copy the version that is present in room K334 in HSC.

Homework exercises

In each exercise class the student will receive a set of obligatory exercises. Students which are unable to visit an exercise class can obtain the exercise from the Linguistics library (HSC room K334) or get via the web page for this course. You have three days for making these exercises. This means that you have to hand them in on Thursday since most exercise classes are on Monday. Exercises which are handed in after the deadline receive one point penalty per extra day. If you are unable to come to the Thursday class you can also put your answer in my mailbox (HSC building across room B390) or send it to me by e-mail.


Students will receive a grade between 0 and 10 for the six exercise class assignments and for the written test at the end of the course. The complete course will be graded with the marks U (failed), G (passed) and VG (passed with distinction). To pass this course the student will have to get an average grade of 6.0 or higher for the exercise class assignments and a grade of 6.0 or higher for the final written test. In order to receive the passed with distinction grade the student should obtain an average for the two grades of 8.0 or higher while neither the average exercise grade nor the grade for the written test may be lower than 7.0.


We will use this book in the course:

The book is permanently available in the library of Institutionen för Lingvistik but I recommend that you buy one for yourself. This course will deal with the chapters 1, 2, 3, 16, 17, 18 and 19.


People that like working with Prolog can obtain some optional course related software from the web page for this course. At this moment the only chapter for which software is available is chapter 17.

Last update: November 23, 1997.