Week 3: Formal Languages and Processes
This page collects the relevant material of the third week of the Foundations of Informatics Bridging Course in Winter 2024/25. It is offered from March 31 to April 4, 2025 as an online course, and covers the following topics:
- Part A: Regular Languages
- Introduction to Formal Languages
- Deterministic and Nondeterministic Finite Automata
- Regular Expressions and Languages
- Closure and Decidability Properties
- Part C: Context-Free Languages
- Context-Free Grammars and Languages
- Relation to Regular Languages
- Pushdown Automata
- Closure and Decidability Properties
Schedule
- Monday, March 31:
- 09:00-09:30: Kick-off meeting via Zoom
- Slides of kick-off
- Remainder of day: Self-paced learning by means of videos
- Tuesday, April 1:
- 09:00-10:30: Questions & exercises via Zoom
- Exercises
- Remainder of day: Self-paced learning by means of videos
- Wednesday, April 2:
- 09:00-10:30: Questions & exercises via Zoom
- Exercises
- Remainder of day: Self-paced learning by means of videos
- Thursday, April 3:
- 09:00-10:30: Questions & exercises via Zoom
- Exercises
- Remainder of day: Self-paced learning by means of videos
- Friday, April 4:
- 09:00-11:00: Questions & exercises via Zoom
- Exercises
Objectives
After passing this part of the course, participants are expected to have acquired the following skills:
- Regular Languages:
- to give the basic definitions of finite automata and regular expressions;
- to construct a finite automaton or a regular expression from a given language description;
- to translate a regular expression into an equivalent finite automaton;
- to compute the set of reachable states of a finite automaton with respect to a given input word;
- to remove ε-transitions from a finite automaton;
- to apply the powerset construction to turn a nondeterministic finite automaton into a deterministic one; and
- to minimise a given deterministic finite automaton.
- Context-Free Languages:
- to give the basic definitions of context-free grammars and pushdown automata;
- to construct a context-free grammar or a pushdown automaton from a given language description;
- to turn a given context-free grammar into Chomsky normal form;
- to apply the CYK algorithm to decide the word problem for a context-free grammar;
- to apply the marking algorithm to decide the emptiness problem for a context-free grammar; and
- to translate a context-free grammar into an equivalent pushdown automaton.
Additional Material
The following exam questions provide an orientation regarding the contents of earlier written exams. The oral exams that we currently offer are somewhat different in style as they discuss more general questions about concepts, formal definitions, algorithmic principles, proof ideas etc. and not so many concrete exercise tasks.
- Exam questions (.zip archive)
In addition, you may want to have a look at the Theory of Computation online course, in particular the following parts:
- Deterministic Finite State Machines: Introduction
- Deterministic Finite State Machines: Examples
- Operations on Regular Languages
- Nondeterministic Finite State Machines: Introduction
- Nondeterministic Finite State Machines: Formal Definition
- Equivalence of Deterministic and Nondeterministic FSMs
- Closure of Regular Operations
- Regular Expressions
- Equivalence of Regular Expressions and Regular Languages
- Context-Free Grammars and Languages
- An Example Context-Free Language and Grammar
- Chomsky Normal Form
- Pushdown Automata
Moreover, the following textbooks provide additional information:
- J.E. Hopcroft, R. Motwani, J.D. Ullmann: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001
- A. Asteroth, C. Baier: Theoretische Informatik, Pearson Studium, 2002 [in German]