Automata and languages
Aktuell/nästa kursomgång: automat12.
Automata and Languages is a 6-point (högskolepoäng) course.
Automata are mathematical machines, that is, abstract computing devices. Their purpose is to capture, study and compare different models and views of the abstract notion of computation and its various aspects. The computational power of automata can be characterized through the classes of languages (that is, sets of strings over a finite alphabet of symbols) they can accept/recognize.
Important notions in computer science like state, nondeterminism and minimization are captured in the simple model of finite automata, which recognize the class of regular languages. Automata provide the basis for the implementation of many programming languages, with parsing being a typical application. Another important reason for studying automata is to capture the notion of effective computability, that is, to characterize the notion of computation as a process which can be physically implemented. This allows the important question to be posed: what problems can be decided algorithmically, and where are the limits to this?
The course is given in English. However, students can use Swedish when writing assignments and exams, and when communicating with the lecturer.
StaffCourse leader and lecturer: Dilian Gurov, e-mail dilian at csc.kth.se, phone 08-790 81 98.
Visiting address: Osquars backe 2, floor 4, room 4417.