SubjectSlidesReadings
Mathematical preliminaries: sets, relations, graphs, induction, contradiction cl1 Linz 1.1 Math Preliminaries
alphabet, strings, formal languages, Deterministic Finite Automata cl2 Linz 1.2 Languages & Grammars & Automata; 2.1 DFA
NFA, ε-NFA, Rabin-Scott powerset construction cl3 Linz 2.2 NFA; 2.3 Equivalence of DFA & NFA
DFA minimization, Linz 2.4 Reduction of the Number of States in FA
Definition of regular expressions, languages denoted by regular expressions are regular, and regular expressions for regular languages. cl4 Linz 3.1 Regular Expressions; 3.2 Equivalence
Regular Grammars; Linear grammars cl5 Linz 3.3 Regular Grammars
Properties of Regular Languages; Pumping lemma for regular languages cl6 Linz 4.1 Closure Properties, 4.2 Questions [Decision Algorithms], 4.3 Pumping Lemma
Applications of Pumping Lemma: wwR, anbmcn+m, an!; Lex cl7 Linz 4.3 Pumping Lemma
Context-Free Languages Context-free language and grammar cl8 Linz 5.1 CFG & CFL, 5.2 Parsing & Ambiguity
Parsing; Simplifications of CFG: substitution, useless productions, nullable, unit productions cl9 Linz 5.2-5.3, 6.1 Methods for Transforming Grammars
Chomsky Normal Form (CNF); Greibach Normal Form (GNF); CYK algorithm for grammars in CNF cl10 Linz 6.2 Two Normal Forms; 6.3 CYK Algo
NPDA; cl10b 7.1 NPDA
NPDAs continued; Equivalence of CFG and PDA. cl11 Linz 7.1 (NPDA), 7.2 (PDA and CFL)
DPDA; Properties of CFL cl12 7.3 Deterministic Pushdown Automata
8.2 Properties and Decision Algorithms
Properties of CFL cl12b 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
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 Linz 9 Turing Machines
Computing Functions with Turing Machines; Church-Turing Thesis cl16 Linz 9.1.3 (TMs as Transducers), 9.2 (Combining TMs)
Variations of Turing Machines;Nondeterministic TM equivalent to Deterministic TM cl17 Linz 10 (Other models of TMs)
Linear Bounded Automata cl18 10.5 Linear Bounded Automata
Universal Turing Machine; length ordered strings; Cantor's diagonal argument; cl18u Linz 10.4 Universal Turing Machine
Recursively enumerable and recursive languages cl19 Linz 11.1 Recursive and Recursively Enumerable Languages
Chomsky Hierarchy; Halting Problem; cl20 Linz 11.2 (Unrestricted grammars)
Halting Problem; cl20d Linz, Chapter 12
Reducibility; Rice's Theorem cl21 Linz 12.1 Unsolvable Problems
Decidability; Post Correspondence Problem cl22 Linz 12.3 The Post Correspondence Problem
Other Models of Computation; mu recursive functions; Post canonical system; Term rewriting; cl23 Linz 13.1 Recursive functions; 13.2 Post Systems; 13.3 Rewriting Systems
Cook's Theorem; Linz 14 An Overview of Computational Complexity