This repository contains my teaching materials for "Automaten & Formale Sprachen" (automata & formal languages) in German. I used them to teach students in tutorials on this subject. There are two sets of slides:
- First version of slides from 2010
- Second, revised version of slides from 2012
The slides cover the following topics:
- Revision of discrete mathematics
- Languages
- Definitions
- Finite automata
- Regular expressions
- Equivalence of automata
- Powerset construction
- Chomsky hierarchy
- Pumping lemma for regular languages
- Minimisation of finite automata
- Grammars
- Chomsky hierarchy
- Chomsky normal form
- Closure properties
- Pumping lemma examples
- Ambiguity of grammars
- Pushdown automata
- Pumping lemma for context-free languages
- Pumping lemma for regular and context-free languages
- Examples of proofs using the pumping lemma
- Turing machines
- Cardinality of classes of languages
- Introduction to complexity theory
The slides cover the following topics:
- Revision of discrete mathematics
- Languages
- Definitions
- Finite automata
- Regular expressions
- Equivalence of automata
- Powerset construction
- Chomsky hierarchy
- Pumping lemma for regular languages
- Minimisation of finite automata
- Grammars
- Chomsky hierarchy
- Chomsky normal form
- Closure properties
- Pumping lemma examples
- Ambiguity of grammars
- Pushdown automata
- Pumping lemma for context-free languages
- Turing machines
- Cardinality of classes of languages
- Introduction to complexity theory