Matematisk Lingvistik VT98

This is an overview of the course Formal Languages and Automata (in Swedish: Matematisk Lingvistik) that will been taught in the Winter term of 1998 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) 4711175, e-mail

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


This 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 could have found optional exercises from this book which you can make to test your comprehension of the lecture material.

       date time  room  subject
 1. må 3003 14-16 A138  Lecture: Ch  1.1-1.7.  Ex  1.1,1.5
 2. ti 3103 14-16 K428  Lecture: Ch  1.8       Ex  1.7,1.9
 3. to 0204 14-16 A110  Exercise class 1 (24/25)
 4. må 0604 14-16 A144  Lecture: Ch  2.1-2.4   Ex  2.1
 5. ti 0704 14-16 A138  Lecture: Ch  3.1-3.2   Ex  3.2
 6. to 0904 14-16 A110  Exercise class 2 (23/25)
 7. ti 1404 14-16 A162  Lecture: Ch  3.3-3.4   Ex  3.1,3.3
 8. on 1504 14-16 A144  Lecture: Ch  3.5       Ex  3.5
 9. to 1604 14-16 A162  Exercise class 3 (22/24)
10. må 2004 14-16 A110  Lecture: Ch 16.1-16.2
11. ti 2104 14-16 A110  Lecture: Ch 16.3       (midcourse evaluation)
12. to 2304 14-16 A110  Exercise class 4 (22/24)
13. må 2704 14-16 A110  Lecture: Ch 16.3-16.6
14. ti 2804 14-16 A110  Lecture: Ch 17.1-17.2  Ex 17.1,17.3,17.10
15. on 2904 14-16 A144  Exercise class 5 (22/24)
16. må 0405 14-16 A110  Lecture: Ch 17.2-17.3  Ex 17.11,17.12
17. ti 0505 14-16 A144  Lecture: Ch 18.1-18.2  Ex 18.1,18.5
18. to 0705 14-16 B113  Exercise class 6 (21/24)
19. må 1105 14-16 A162  Lecture: Ch 18.3-18.4  Ex 18.3
20. ti 1205 14-16 A144  Lecture: Ch 18.5-18.6
21. to 1405 14-16 B113  Exercise class 7 (21/24)
22. må 1805 14-16 A110  Lecture: Ch 19.1-19.4  Ex 19.1,19.3
23. ti 1905 14-16 A144  Lecture: Ch 19.5-19.7  (final evaluation)
24. on 2005 14-16 A144  Exercise class 8 (6/24)
    må 2505 09-13 MagB  Test (20/24)
    ?? ??08             Extra test

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.

The test will take place in room B of the Magistern building, Dag Hammarskjölds väg 31, Uppsala, phone (018) 471 7337.

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 students 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 them via the web page for this course. You have five days for making the exercises. This means that you have to hand them in on Tuesday since most exercise classes are on Thursday. Exercises which are handed in after the deadline receive one point penalty per extra day. If you are unable to come to the Tuesday class you can also put your answers in my mailbox (HSC building across room B390), send it by e-mail to or send it by fax to number (018) 4711416.


Students will receive a grade between 0 and 10 for the eight 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 (well passed). 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 well pass grade the student should obtain an average for the two grades of 8.0 or higher while the grade for the written test is also 8.0 or higher.


We will use this book in the course:

The book is permanently available in the library of the Linguistics department but I recommend that you buy one for yourself. The book cost approximately SEK 650 in 1996. 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: May 31, 1998.