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 |