Mathematical Foundations of Computational Linguistics II: Formal Languages and Automata

(Diese Seite gibt es auch auf Deutsch.)

Lecture with exercise session
B.Sc. in Computational Linguistics
Instructors: Werner Saurer, Stefan Thater

Lec Mon 14:15-15:45, Wed 13:15-14:00; Ex Wed 16:00-17:30
Lec: Building C 72, seminar room
Ex: Building C 72, seminar room
First meeting: Wed 11 April 2018


The course introduces the various types of languages and grammars (regular, context-free, context-sensitive, type-0-grammars) on the one hand and presents the corresponding types of abstract automata (finite automata, push-down-automata, Turing-machines) on the other.

Special emphasis will be on the command of the various formalisms, from a practical as well as theoretical perspective.


Mathematical Foundations I. Students who haven't completed this course should consult with the instructor first.

Text books

Partee, B., A. ter Meulen, R.Wall, Mathematical Methods in Linguistics. Dordrecht: Kluwer 1990.
Lewis, H.R./C.H. Papadimitriou, Elements of the Theory of Computation. New Jersey: Prentice Hall 1981.

Position in degree programs

Computational Linguistics B.Sc. program: obligatory course. There will be a midterm and a final exam (45 min each).For details see German version. 8 credit points (Leistungspunkte)

Exercise session

Wed 16-18, building C 72, seminar room; date of first meeting will be announced.
Course mechanics and detailed lecture plan (in German only)

Office hours

Wed 14-15, Building C 72, Room 0.07, Tel. 302-4177
Werner Saurer

Wed 14-15, Building C 72, Room 1.11, Tel. 302-4496
Stefan Thater