afs

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

2012

The slides cover the following topics:

1. AFS 0

• Revision of discrete mathematics

2. AFS I

• Languages
• Definitions
• Finite automata
• Regular expressions

3. AFS II

• Equivalence of automata
• Powerset construction
• Chomsky hierarchy
• Pumping lemma for regular languages
• Minimisation of finite automata

4. AFS G

• Grammars
• Chomsky hierarchy
• Chomsky normal form

5. AFS III

• Closure properties
• Pumping lemma examples

6. AFS IV

• Ambiguity of grammars
• Pushdown automata
• Pumping lemma for context-free languages

7. AFS PL

• Pumping lemma for regular and context-free languages
• Examples of proofs using the pumping lemma

8. AFS V

• Turing machines
• Cardinality of classes of languages

9. KOMP

• Introduction to complexity theory

2010

The slides cover the following topics:

1. AFS 0

• Revision of discrete mathematics

2. AFS 1

• Languages
• Definitions
• Finite automata
• Regular expressions

3. AFS 2

• Equivalence of automata
• Powerset construction
• Chomsky hierarchy
• Pumping lemma for regular languages
• Minimisation of finite automata

4. AFS G

• Grammars
• Chomsky hierarchy
• Chomsky normal form

5. AFS 3

• Closure properties
• Pumping lemma examples

6. AFS 4

• Ambiguity of grammars
• Pushdown automata
• Pumping lemma for context-free languages

7. AFS 5

• Turing machines
• Cardinality of classes of languages

8. KOMP

• Introduction to complexity theory