Automata and Formal Languages
Module IN2041
This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
Module version of WS 2011/2
There are historic module descriptions of this module. A module description is valid until replaced by a newer one.
Whether the module’s courses are offered during a specific semester is listed in the section Courses, Learning and Teaching Methods and Literature below.
| available module versions | |
|---|---|
| WS 2015/6 | WS 2011/2 |
Basic Information
IN2041 is a semester module in English language at Bachelor’s level and Master’s level which is offered in winter semester.
This Module is included in the following catalogues within the study programs in physics.
- Catalogue of non-physics elective courses
| Total workload | Contact hours | Credits (ECTS) |
|---|---|---|
| 240 h | 90 h | 8 CP |
Content, Learning Outcome and Preconditions
Content
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 Outcome
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.
- 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.
Preconditions
IN0011 Introduction to Theory of Computation
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
WS 2022/3
WS 2021/2
WS 2020/1
WS 2019/20
WS 2018/9
WS 2017/8
WS 2016/7
WS 2015/6
WS 2013/4
WS 2012/3
| Type | SWS | Title | Lecturer(s) | Dates | Links |
|---|---|---|---|---|---|
| VU | 6 | Automata and Formal Languages (IN2041) | Esparza Estaun, F. |
Thu, 14:00–16:00, MI 02.13.010 Mon, 10:00–12:00, MI 02.13.010 Tue, 12:00–13:30, MI 02.13.010 and singular or moved dates |
Learning and Teaching Methods
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.
Media
Slide show, blackboard, tool presentations, written assignments.
Literature
Javier Esparza: Automata Theory --- An algorithmic approach. Lecture notes, 2012.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; Introduction to Automata Theory, Languages and Computation; Addison-Wesley Longman, 3rd edition, 2006.
Joerg Flum, Erich Graedel, Thomas Wilke (eds.); Logic and Automata: History and Perspectives, Volume 2; Amsterdam University Press, 2008.
Dominique Perrin, Jean-Eric Pin; Infinite Words: Automata, Semigroups, Logic and Games; Academic Press, 2004.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; Introduction to Automata Theory, Languages and Computation; Addison-Wesley Longman, 3rd edition, 2006.
Joerg Flum, Erich Graedel, Thomas Wilke (eds.); Logic and Automata: History and Perspectives, Volume 2; Amsterdam University Press, 2008.
Dominique Perrin, Jean-Eric Pin; Infinite Words: Automata, Semigroups, Logic and Games; Academic Press, 2004.
Module Exam
Description of exams and course work
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.
Exam Repetition
The exam may be repeated at the end of the semester.