| Subject | Slides | Video | Readings |
|---|---|---|---|
| Mathematical preliminaries: sets, relations, graphs, induction, contradiction | cl1 | Linz 1.1 Math Preliminaries | |
| alphabet, strings, formal languages | cl2 | § 1.2 | Linz 1.2 Languages & Grammars |
| Deterministic Finite Automata | cl2 | § 2.1 | Linz 2.1 DFA |
| NFA, ε-NFA | cl3 | § 2.2 | Linz 2.2 NFA |
| Rabin-Scott powerset construction | cl3 | § 2.3 | Linz 2.3 Equivalence of DFA & NFA |
| DFA minimization, | min | § 2.4 | Linz 2.4 Reduction of the Number of States in FA |
| Simple closure properties of regular languages | § 4.1 | Linz 4.1 Closure Properties | |
| Regular Expressions | regular | Linz 3.1 Regular Expressions | |
| Definition of regular expressions. | cl4 | § 3.1 | Linz 3.1 Regular Expressions |
| Languages denoted by regular expressions are regular, and regular expressions for regular languages (generalized transition graph). | cl4 | § 3.2 | Linz 3.2 Equivalence |
| Introduction to Grammars | grammar | grammar | Introduction to Grammars |
| Regular Grammars, Linear grammars | cl5 | Linz 3.3 Regular Grammars | |
| Properties of Regular Languages; Pumping lemma for regular languages | cl6 | § 4.1 § 4.2 § 4.3 |
Linz 4.1 Closure Properties, 4.2 Questions [Decision Algorithms], 4.3 Pumping Lemma |
| pump-reg | pump | Formal Statement of Pumping Lemma and Proof Template | |
| Applications of Pumping Lemma: wwR, anbmcn+m, an!; | cl7 | § 4.3 | Linz 4.3 Pumping Lemma |
| Context-Free Languages Context-free language and grammar. Derivation tree | cl8 | § 5.1 § 5.2 |
Linz 5.1 CFG & CFL, 5.2 Parsing & Ambiguity |
| Parsing; Simplifications of CFG: substitution, useless productions, nullable, unit productions | cl9 | § 5.2 | Linz 5.2-5.3, 6.1 Methods for Transforming Grammars |
| Chomsky Normal Form (CNF); Greibach Normal Form (GNF); | cl10 | § 6.2 | Linz 6.2 Two Normal Forms |
| CYK algorithm for grammars in CNF | in cfg | cyk | Linz 6.3 CYK Algo |
| PDA; |
cl10b cl11 |
§ 7.1 § 7.1 |
Linz 7.1 PDA |
| Equivalence of CFG and PDA. | cl11b | Linz 7.2 PDA and CFL | |
| DPDA; Positive and negative properties of CFL | cl12 | Linz 7.3 Deterministic Pushdown Automata Linz 8.1 Properties and Decision Algorithms |
|
| Negative properties of CFL | cl12b | 8.2 | Linz 8.2 Closure Properties and Decision Algorithms |
| Applications of Regular Closure; Decidable Properties of Context-Free Languages | cl13a | Linz 8.2 Closure Properties and Decision Algorithms; Example 8.7 | |
| The Pumping Lemma for CFL; Example anbncn | cl13b | Linz 8.1: Pumping Lemma for Context-Free Languages | |
| pump-cfl | pump | Formal Statement of Pumping Lemma for CFL | |
| Applications of the Pumping Lemma: ww, an!, an2bn; | cl14 | Linz 8.1: Pumping Lemma for Context-Free Languages | |
| Pumping Lemma for Linear Languages | Linz 8.1: Pumping Lemma for Linear Languages | ||
| Turing Machines; Combining Turing Machines; | cl15 |
§ 9.1 § 9.1 |
Linz 9 Turing Machines |
| Computing Functions with Turing Machines; Church-Turing Thesis | cl16 | § 9.2 | Linz 9.1.3 (TMs as Transducers), 9.2 (Combining TMs) |
| Variations of Turing Machines; Nondeterministic TM equivalent to Deterministic TM | cl17 |
§ 10.1 § 10.2 |
Linz 10.1, 10.2, 10.3 (Other models of TMs) |
| Linear bounded automaton | cl18 | 10.5 Linear Bounded Automata | |
| Universal Turing Machine; length ordered strings; Cantor's diagonal argument; | cl18 |
§ 10.4 § 10.4 | Linz 10.4 Universal Turing Machine |
| Recursively enumerable and recursive languages | cl19 | § 11.1 | Linz 11.1 Recursive and Recursively Enumerable Languages |
| Chomsky Hierarchy; | cl20 | § 11.2, 11.3 | Linz 11.2 Unrestricted Grammars, 11.3 Context-Sensitive Grammars |
| Decision_problem; Halting problem | cl20 | § 12.1 | Linz, Chapter 12 |