DD2372 Automata and Languages 6.0 credits

Automater och språk

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?

Show course information based on the chosen semester and course offering:

Offering and execution

No offering selected

Select the semester and course offering above to get information from the correct course syllabus and course offering.

Course information

Content and learning outcomes

Course contents *

Part I. Finite Automata and Regular Languages: determinisation, model checking, regular expressions, state minimization, proving non-regularity with 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, proving non-context-freeness with the pumping lemma, pushdown automata.

Part III. Turing Machines and Effective Computability: Turing machines, recursive sets, universal Turning machines, decidable and undecidable problems, Rice's theorem, other models of effective computability.

Intended learning outcomes *

The overall aim of the course is to provide students with a profound understanding of computation and effective computability through the abstract notion of automata and the language classes they recognize. Along with this, the students will get acquainted with the important notions of state, nondeterminism and minimization.

After the course, the students will be able to:

1) Account for the main classes of automata and structural representations (regular expressions and grammars) and the corresponding language classes: Construct an automaton or a grammar from an informal language description [for grade E].

2) Relate the various classes by means of language-preserving transformations; apply the transformations for solving concrete problems: Apply the transformations on concrete examples [E], define new transformations [C], prove the transformations to be language-preserving [A].

3) For each language class, explain the main characterisation theorems; apply the theorems for solving concrete problems: Explain the easier theorems on concrete examples [E], explain the more difficult theorems on concrete examples [C], apply the theorems to prove various language properties [A].

Course Disposition

No information inserted

Literature and preparations

Specific prerequisites *

No information inserted

Recommended prerequisites

SF1610/SF1630/SF1688 Discrete Mathematics and DD1350 Logic for Computer Science, or the equivalent.

Equipment

No information inserted

Literature

Hopcroft, Motwani and Ullman "Introduction to Automata theory, Languages and Computation", 3rd Edition, Addison-Wesley, 2007, ISBN: 0-321-47617-4.

Examination and completion

Grading scale *

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

Examination *

  • HEMA - Exercises, 2.5 credits, Grading scale: P, F
  • LABA - Laboratory work, 2.0 credits, Grading scale: P, F
  • TENA - Examination, 1.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.

In this course all the regulations of the code of honor at the School of Computer science and Communication apply, see: https://www.kth.se/en/csc/utbildning/hederskodex/.

Other requirements for final grade *

Laboratory work (LAB1), home assignments including workshop (HEMA), and examination (TENA).

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Dilian Gurov

Further information

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web DD2372

Offered by

EECS/Computer Science

Main field of study *

Computer Science and Engineering

Education cycle *

Second cycle

Add-on studies

No information inserted

Contact

Dilian Gurov, e-post: dilian@csc.kth.se, tel: 790 8198

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.

Supplementary information

The course has replaced DD2371 Theory of Automata.

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