DD2371 Theory of Automata 6.0 credits

Automatteori

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 example for the application of pushdown automata, which recognize the more powerful class of context-free languages. 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 most influential model for studying these issues is Turing machines.

Offering and execution

Course offering missing for current semester as well as for previous and coming semesters

Course information

Content and learning outcomes

Course contents *

  • Part I. Finite Automata and Regular Languages: determinisation, regular expressions, state minimization, proving non-regularity with the pumping lemma, Myhill-Nerode relations.
  • Part II. Pushdown Automata and Context-Free Languages: context-free grammars and languages, normal forms, 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, reduction, other models of 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 successful student will be able to perform the following constructions:

1. Determinize and minimize automata;

2. Construct an automaton for a given regular expression;

3. Construct a pushdown automaton for a given context-free language;

4. Construct a Turing machine deciding a given problem,

5. Prove whether a language is or isn't regular or context-free by using the Pumping Lemma;

6. Prove that a given context-free grammar generates a given context-free language;

7. Prove undecidability of a given problem by reducing from a known undecidable problem,

8. Apply the fundamental theorems of the course: Myhill-Nerode, Chomsky-Schützenberger, and Rice's theorems.

For passing the course, a student has to be proficient at problems of type 1-5; for the highest grade he/she has to be equally proficient at the remaining types of problems.

Course Disposition

No information inserted

Literature and preparations

Specific prerequisites *

No information inserted

Recommended prerequisites

5B1118/SF1610 Discrete Mathematics, mandatory
5B1928/SF1642 Logic, recommended

Equipment

No information inserted

Literature

Dexter Kozen: Automata and Computability, Springer, 1997.

Examination and completion

Grading scale *

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

Examination *

  • TEN1 - Examination, 6.0 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.

Other requirements for final grade *

Examination (TEN1; 6 university credits).

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

No information inserted

Offered by

CSC/Computer Science

Main field of study *

No information inserted

Education cycle *

Second cycle

Add-on studies

No information inserted

Contact

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

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

This course has been replaced by DD2372 Automata and Languages.