| Subject | Slides | Readings |
|---|
| Mathematical Preliminaries |
ch01 |
Linz 6th, Chapter 1: Introduction to the Theory of Computation |
|
|
ch02 |
Linz 6th, Chapter 2: Finite Automata |
|
|
|
ch03 |
Linz 6th, Chapter 3: Regular Languages and Regular Grammars |
|
ch04 |
Linz 6th, Chapter 4: Properties of Regular Languages |
|
ch05 |
Linz 6th, Chapter 5: Context-Free Languages |
|
ch06 |
Linz 6th, Chapter 6: Simplication of Context-Free Grammars and Normal Forms |
|
ch07 |
Linz 6th, Chapter 7: Pushdown Automta |
|
The Pumping Lemma for CFL
|
ch08
| Linz 6th, Chapter 8: Properties of Context-Free Languages |
|
Church-Turing Thesis
|
ch09 |
Linz 6th, Chapter 9: Turing Machines |
|
Universal Turing Machine;
|
ch10 |
Linz 6th, Chapter 10: Other Models of Turing Machines |
|
ch11 |
Linz 6th, Chapter 11: A Hierarchy of Formal Languages and Automata |
| Post Correspondence Problem |
ch12 |
Linz 6th, Chapter 12: Limits of Algorithmic Computatin |
|
ch13 |
Linz 6th, Chapter 13: Other Models of Computation |
|
ch14 |
Linz 6th, Chapter 14: An Overview of Computational Complexity |