Automata and Languages is a 6-point (högskolepoäng) course on the advanced level. It is coordinated together with its research-level version for doctoral students under the same name, but with course code DD3372.
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.
Staff
Course leader and lecturer: Dilian Gurov, e-mail
dilian at csc.kth.se, phone 08-790 81 98.
Visiting address: Osquars backe 2, floor 5, room 4520.