Skip to main content

DD2373 Automata and Languages 7.5 credits

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 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?

Choose semester and course offering

Choose semester and course offering to see current information and more about the course, such as course syllabus, study period, and application information.

Application

For course offering

Spring 2024 automat24 programme students

Application code

61144

Headings with content from the Course syllabus DD2373 (Spring 2024–) are denoted with an asterisk ( )

Content and learning outcomes

Course contents

Part I. Finite automata and regular languages: determinisation, model checking, regular expressions, state minimization, the pumping lemma, Myhill-Nerode Theorem, regular inference.

Part II. Pushdown automata and context free languages: context-free grammars and languages, parsing, Chomsky-Schützenberger Theorem, modelling the behaviour of programs with recursion, the pumping lemma, pushdown automata.

Part III. Turing machines and efficient computability: Turing machines, recursive sets, universal Turing machines, decidable and undecidable problems, Rice's theorems, other models for effective computability.

Intended learning outcomes

After passing the course, the student shall be able to

1) give an account of the main classes of automata and structural representations (regular expression and grammars) and the equivalent language classes, and design an automaton or a grammar from an informal language description

2) relate the different classes by means of language-preserving transformations, apply the transformations to solve concrete problems and apply the transformations on concrete examples 

3) for each language class, explain the main characterisation theorems, apply the theorems to solve concrete problems and explain simple theorems on concrete examples.

For higher grades, the student should also be able to

  • define new language-preserving transformations [C] and show that the transformations are language-preserving [A]
  • for each language class, explain more difficult theorems on concrete examples [C] and apply the theorems to prove different language properties [A].

Literature and preparations

Specific prerequisites

Knowledge in algorithmic complexity, 6 higher education credits, equivalent to completed course DD2350/DD2352.

Knowledge in discrete mathematics, 6 higher education credits, equivalent to completed course SF1688/SF1610/SF1630/SF1662/SF1679.

Course from Upper Secondary School equivalent to the Swedish upper secondary course English B/6.

Recommended prerequisites

No information inserted

Equipment

No information inserted

Literature

No information inserted

Examination and completion

If the course is discontinued, students may request to be examined during the following two academic years.

Grading scale

A, B, C, D, E, FX, F

Examination

  • HEM1 - Home assignments, 2.5 credits, grading scale: P, F
  • LAB1 - Laboratory work, 2.5 credits, grading scale: P, F
  • TEN1 - Home exam, 2.5 credits, grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Ethical approach

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

Further information

Course room in Canvas

Registered students find further information about the implementation of the course in the course room in Canvas. A link to the course room can be found under the tab Studies in the Personal menu at the start of the course.

Offered by

Main field of study

Computer Science and Engineering

Education cycle

Second cycle

Add-on studies

No information inserted

Supplementary information

In this course, the EECS code of honor applies, see:
http://www.kth.se/en/eecs/utbildning/hederskodex