Automata Theory and Formal Languages (AFS)

Behind the Logic of Software: Learn how software is structured, develop your own formal models, and use them to solve complex computational and software engineering problems.

Contents

• This course provides an introduction to automata theory and the theory of formal languages. Automata theory is the study of abstract computational models. Before the advent of modern computers, Alan Turing developed an abstract machine with the capabilities of today`s computers. The goal was to distinguish between what a machine can compute and what it cannot. During the 1940s and 1950s, simpler computational models, now known as finite automata, were studied and proved to be extremely useful for various applications. At the same time, the linguist Noam Chomsky began studying formal grammars, which are closely related to abstract automata. Some of these concepts, such as finite automata and certain classes of formal grammars, are now widely used in the design and implementation of software. In addition to proof techniques, the course covers the fundamentals of automata theory and formal languages through practical examples. Topics include deterministic and nondeterministic finite automata, pushdown automata, regular expressions and regular languages, context-free and context-sensitive languages, as well as Turing-recognizable and Turing-decidable languages.

Competencies

Students are able to

• describe the fundamentals of automata theory and formal languages.
• identify the language recognized by a given automaton or grammar and define an appropriate automaton or grammar for a given language.
• describe the different types of finite automata and formal languages, understand their properties, and apply the corresponding transformation algorithms.

Literature

• U. Schöning, "Theoretische Informatik – kurz gefasst", 5th ed. Heidelberg, Germany: Spektrum Akademischer Verlag, 2008.
• B. Hollas, "Grundkurs Theoretische Informatik: Mit Aufgaben und Anwendungen", 2nd ed. Berlin, Germany: Springer Vieweg, 2015.
• E. A. Rich, "Automata, Computability and Complexity: Theory and Applications". Upper Saddle River, NJ, USA: Pearson Prentice Hall, 2008.
• C. Baier and A. Asteroth, "Theoretische Informatik: Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen". Munich, Germany: Pearson Studium, 2019.
• G. Vossen and K.-U. Witt, "Grundkurs Theoretische Informatik: Eine anwendungsbezogene Einführung", 6th ed. Wiesbaden, Germany: Springer Vieweg, 2016.
• D. W. Hoffmann, "Theoretische Informatik", 5th ed. Munich, Germany: Carl Hanser Verlag, 2022.
• J.-É. Pin, Ed., "Handbook of Automata Theory", vols. I–II. Berlin, Germany: EMS Press, 2021.
• P. Linz and S. H. Rodger, "An Introduction to Formal Languages and Automata" , 7th ed. Burlington, MA, USA: Jones & Bartlett Learning, 2023.
• B. Barak, "Introduction to Theoretical Computer Science". Cambridge, MA, USA: self-published (open access), 2023. [Online]. Available: https://introtcs.org

Lecturer

• Prof. Dr. Lutz Strüngmann

Recommended Previous Knowledge 

• Fundamentals of theoretical computer science and mathematics

Module Details

Semester	6/7
Lecture Language	German
Frequency	Not regularly
Credit Points (ECTS)	5
Course Coordinator	Prof. Dr. Lutz Strüngmann
Duration	1 Semester
Course Achievement	None
Prerequisite for exam	Compulsory Assignment (PU)
Exam	Written Exam 90 Minutes (K90)

Weekly Hours (SWS) 

Lecture	2 SWS
Exercises	2 SWS
Sum	4 SWS

Work Load 

Lecture	20 h
Lab	40 h
Self Study	60 h
Assignments	30 h
Sum	150 h