| Subject | Slides | Video | Readings. Automata Theory, Lang & C, HMU 3rd, 2007 |
|---|
| Introduction |
PDF |
1-1-1 |
Chapter 1: Automata |
| Introduction to Automata |
PDF |
1-2-2 |
Section 2.1: An Informal Picture of Finite Automata |
| Deterministic Finite Automata |
PDF |
1-3-3 |
Section 2.2: Deterministic Finite Automata |
|
NFA,
ε-NFA,
Rabin-Scott subset construction
|
PDF |
1-4-4 |
Sections 2.3: Nondeterministic Finite Automata |
| Regular Expressions and Languages |
PDF |
2-1-5 |
Section 3.1 Regular Expressions,
Section 3.2 Finite Automata and Regular Expressions,
Section 3.3 Applications of Regular Expressions,
Section 3.4 Algebraic Laws for Regular Expressions.
|
| Properties of Regular Languages |
PDF |
2-3-7 |
Sections 4.1: Proving Languages Not to Be Regular, 4.3: Decision Properties of Regular Languages, 4.4: Equivalence and Minimization of Automata
|
| Closure Properties of Regular Languages |
PDF |
2-4-8 |
Section 4.2: Closure Properties of Regular Languages |
| Context-Free Languages |
PDF |
3-1-9 |
Section 5.1: Context-Free Grammars |
| Parse Trees |
PDF |
3-2-10 |
Sections 5.2, 5.4 |
| Normal Forms for Context-Free Grammars |
PDF |
| Section 7.1 |
| Pushdown Automata |
PDF |
3-4-12 |
Sections 6.1, 6.2 |
| Equivalence of CFG's and PDA's |
PDF |
| Section 6.3: Equivalence of CFG's and PDA's |
| The Pumping Lemma for Context-Free Languages |
PDF |
4-2-14 |
Section 7.2 |
| Properties of Context-Free Languages |
PDF |
| Sections 7.3, 7.4 |
| Enumerations, Turing Machines |
PDF |
| Sections 8.1, 8.2 |
| More About Turing Machines |
PDF |
| Sections 8.3 - 8.6 |
| Undecidable Problems |
PDF |
| Sections 9.1, 9.2 |
| More Undecidable Problems |
PDF |
| Sections 9.3 - 9.5 |
| NP-Completeness |
PDF |
| Section 10.1 |
| Satisfiability, Cook's Theorem |
PDF |
| Sections 10.2, 10.3 |
|
| More NP-Complete Problems |
PDF |
| Sections 10.4, 11.1 |
| PSPACE-Complete Problems |
PDF |
| Sections 11.2, 11.3 |