SubjectSlidesReadings
Mathematical preliminaries: sets, relations, graphs, induction, contradiction cl1 Linz 1.1 Math Preliminaries
alphabet, strings, formal languages, Deterministic Finite Automta 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
Definition of regular expressions 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, 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; PDA; NPDA; cl10 Linz 6.2 Two Normal Forms; 6.3 CYK Algo; 7.1 NPDA
NPDAs continued; Equivalence of CFG and PDA. cl11 Linz 7.1 (NPDA), 7.2 (PDA and CFL)
PDA; Properies of CFL cl12 Linz 7.2-8.2 (Properties and Decision Algorithms)
Applications of Regular Closure; The Pumping Lemma for CFL; Example anbncn cl13 Linz 7.2-8.2
Applications of the Pumping Lemma: ww, an!, an2bn; YACC cl14 Linz 8: Properies of Context-Free 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 (LBAs)
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
Chomsky Hierarchy; Halting Problem; cl20 Linz 11.2 (Unrestricted grammars)
Reducibility; Rice's Theorem cl21 Linz 12.1 (Unsolvable Problems)
Decidability; Post Correspondence Problem cl22 Linz
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 Systmes)