EduXchange.EU

Automata and Formal Languages

IN2041
Computer Science and ICT, Data, AI

About this course

The module is divided into two parts. The first part deepens and expands the study of finite automata initiated in IN0011 (Introduction to theoretical computer science), while the second introduces automata on infinite words. In both parts automata are seen as a data structure for the manipulation of (possibly infinite) sets and relations. The module shows how to implement Boolean operations and joins for different automata classes (nondeterministic and deterministic automata, binary decision diagrams, Büchi automata). It also introduces the connection between automata and logic. The algorithms are applied to a variety of problems, ranging from pattern-matching to program verification and solution of Diophantine equations.

Learning outcomes

On successful completion of the module, students will be able to

  • use finite automata as a data structure for representation of finite and infinite sets;
  • understand and determine the computational complexity of different operations for different classes of automata;
  • move to and fro logical and automata-theoretic descriptions;
  • apply automata to problems in pattern matching and formal verification.

Examination

Students are assessed by means of a written 120 minutes exam consisting of a list of exercises. Some exercises test if the students are able to construct finite automata for different languages, directly or with the help of composition operations. Other exercises test if the student knows and can apply and combine the algorithms to move between logical and automata-theoretic descriptions. Other exercises test if students can select the right automata-theoretic technique to solve problems related to verification and pattern-matching.

Course requirements

IN0011 Introduction to Theory of Computation

Activities

The module consists of lectures and tutorials. During the lectures students are asked to solve small exercises online. Students also received weekly assignments, whose solution is discussed in the tutorials.

Additional information

  • Credits
    ECTS 8
  • Contact hours per week
    4
  • Instructors
    Jan Kretinsky, Balasubramanian Ayikudi Ramachandrakumar, Philipp Czerner, Ernst Mayr, Systemadministrator, Francisco Javier Esparza Estaun, Salomon Sickert - Zehnter, Marijana Lazic, Chana Weil-Kennedy, Moritz Fuchs, Roland Guttenberg
  • Mode of instruction
    Hybrid
If anything remains unclear, please check the FAQ of TUM (Germany).

Offering(s)

  • Start date

    15 October 2024

    • Ends
      4 February 2025
    • Term *
      Winter 2024/2025
    • Instruction language
    • Register between
      24 May - 29 Jul 2024
    Only 7 days to enrol
    Apply now
These offerings are valid for students of DTU (Denmark)