Theory of Computation

Computer science as a science.

Notes

• Course taught by Nick Cheng
• 5 Tutorial sections
• Tutorials lag behind by one week
• OH: https://cmsweb.utsc.utoronto.ca/nick/timetable.html
• https://www.cs.toronto.edu/~vassos/b36-notes/notes.pdf
• https://cmsweb.utsc.utoronto.ca/nick/cscB36/additional-notes/
• Exam seats are randomly assigned
• FYOG Assignments dont count for marks
• Problem sets are used only for extra marks, they are posted collectively on piazza, they are worth 10%
• Final exam 40%
• Term test 1 20% (Oct 4 9-10:30AM)
• Term test 2 20% (Nov 10, 5-6:30PM)
• The media gallery has 2021 videos for future review
• Everytime you use a Indirect Proof, you must explitly show
• Never use CSCB58 $+,\cdot$ versions of And, Or, use mins and max instead

Concepts

Week 1

• Mathematical Maturity
• Math Proof
• Atomic Symbols
• Mathematical Statement
• Logical Predicate
• Universal Instantiation
• Witness
• Indirect Proof
• Implies
• Or
• Such That
• Twin Prime
• Twin Prime Conjecture
• Halting Problem
• Cartesian Product
• Relation
• Arity
• Set Cardinality

Week 2

• Binary String
• Counting Odd Parity Substrings from Given Binary String
• Simple Induction
• Stamps Simple Induction Example
• Stamps Strong Induction Example
• Unwinding Recurrence
• Master Theorem
• Principle of Well-Ordering
• Proof by Structural Induction
• Smallest Set

Week 3

• Pascal
• Program Correctness
• Loop Invariant
• Iterative Program Correctness
• Recursive Program Correctness
• Pythonized Lemma 2

Week 4

• Nothing new, just practice

Week 5

• Empty String
• Terminating Variable
• Symbol
• Alphabet
• Powers of Sigma
• String
• Language
• Regular Language
• Regular Expression
• Language of Regex
• Semantics of Regular Expressions
• Multiset
• Regex Precedences
• Regex to Match All Strings
• Regex to Match Even Length Strings
• Regex to Match Strings that Start and End with 1
• Equivalent Regex
• Language Function
• Closure of Regular Expressions

Week 6

• State Space
• Automata Theory
• Deterministic Finite Automaton
• Language of FSA
• Pigeonhole Principle
• Transition Function
• Extended Transition Function
• Specification
• Documentation
• Final State
• Reachable State
• Dead State
• NFSA
• Big Result
• Subset Construction

Week 7

• FSA Complement
• FSA Union
• Cartesian Product Construction
• State Space Cartesian Product
• FSA Concatenation
• FSA Kleene Star
• Proving Closure Property using FSA
• Pumping Lemma
• Ogden’s Lemma
• Occurance Notation

Week 8

• Grammar
• Context Free Grammar
• Terminal
• Non-terminal
• Grammar Derivation
• Language of a Context Free Grammar
• CFL
• Parse Tree
• Ambiguous Context Free Grammar
• Inherently Ambiguous Context Free Grammar
• Finding CFG Example
• Left to Right Method
• Finding CFG Example 2
• Right-Linear Grammar
• The Big Result Plus

Week 9

• Evan’s Language Verifier
• Pushdown Automata
• PDA Accepting a String
• Deterministic PDA
• PDA Configuration

Week 10

• Proposition
• Logical Connectives
• Propositional Variable
• Propositional Formula
• Truth Assignment
• Extended Truth Assignment
• Parse Tree
• Truth Table
• Nick’s Truth Table Structure
• Proposition Conventions
• Satisfies
• Falsifies
• Formula Logical Implication
• Formula Logical Equivalence
• Literal
• Normal Form
• Term
• Propositional Clause
• Disjunctive Normal Form
• Conjunctive Normal Form
• DNF Theorem
• CNF Theorem
• Boolean Function
• Formula Representing Boolean Function
• Complete Set of Boolean Connectives
• Connective Set Completeness Reduction

Extra (Neso Academy)

• Turing Machine
• Undecidable
• Chomsky Hierarchy
• Arden’s Theorem