PREV

• Week 1: Mathematical Tools and Techniques: Logic and Proofs, Sets, Functions and Equivalence Relations, Languages.
• Week 2: Proofs, Principle of Mathematical Induction, Recursive Definitions, Structural Induction.
• Week 3: Regular Languages and Regular Expression
• Week 4: Nondeterministic Finite Automata with A-Transitions, Kleene’s Theorem.
• Week 5: Regular, Non-regular Languages, Criteria for Regularity, Minimal Finite Automata
• Week 6: Context-Free Grammars, Regular Grammars, Derivation Tree and Ambiguity
• Week 7: Pushdown Automata: Definitions and Examples, Deterministic Pushdown Automata
• Week 8: Context-Free, Non-Context-Free Languages.
• Week 9: Turing Machines: Definitions and Examples, Non-deterministic TM, Universal TM
• Week 10: Recursively Enumerable and Languages: Recursively Enumerable and Recursive, Enumerating a Language, More General Grammars, Context-Sensitive Languages and the Chomsky Hierarchy
• Week 11: Unsolvable Problems: A No-recursive Language and an Unsolvable Problem, The Halting Problem, Unsolvable Problems Involving TMs, Rice’s Theorem, Post’s Correspondence Problem
• Week 12: Computable Functions: Primitive Recursive Functions, PRF and Bounded Operations, Unbounded. Minimalization and ų-Recursive Functions, Godel Numbering