Mathematical Foundations of Computational Linguistics II: Formal Languages and Automata

(https://www.coli.uni-saarland.de/~saurer/lehre/ss00/mg2/mg2-engl-ss00.html)
(Diese Seite gibt es auch auf Deutsch.)

Lecture with exercise session
First stage
Instructor: Werner Saurer

Lec Mon 14-16, Wed 13-14; Ex Wed 16-18
Lec: Building 17.2, seminar room
Ex: Room will be announced
First meeting: Wed 12 April 2000

Content

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.

Prerequisites

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 diploma program: obligatory course. There will be a midterm and a final exam (45 min each).For details see German version. 5 credit points (Leistungspunkte)

Exercise session

Wed 16-18, Room will be announced; first meeting: 19 April 2000.

Office hours

Wed 14-15, Building 17.2, Room 1.08, Tel. 302-4177
E-mail Werner Saurer