Automata and Languages

Log in to your course web

You are not logged in KTH, so we cannot customize the content.

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 formal languages (that is, sets of strings over a finite alphabet of symbols) they can accept/recognize.

Important notions in computer science like state, non-determinism 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.

The course is coordinated together with its research-level version for doctoral students under the same name, but with course code FDD3372.

Teachers

Feedback News