Automata, Formal Languages and Complexity

Jörg Endrullis
Vrije Universiteit Amsterdam

Introduction
Languages
Finite Automata
Regular Grammars
Regular Expressions
Properties of Regular Languages
Word Matching
Minimization of Deterministic Finite Automata (DFAs)
Pumping Lemma for Regular Languages
Context-free Grammars
Chomsky Normal Form
CYK Parsing
LL Parsing
Nondeterministic Pushdown Automata
Pumping Lemma for Context-free Languages
Properties of Context-free Languages
Turing Machines
Properties of Recursively Enumerable Languages
Unrestricted Grammars
Context-sensitive Grammars and Linear Bounded Automata
Chomsky Hierarchy
Undecidability
Time and Space Complexity