The course is mathematical/theoretical in nature. The knowledge you gained in COMP283/MATH381/STOR315 will help in this course. The other name for this course is "Theory of Computation".
The below is taken from Professor PS Thiagarajan's syllabus.
Content
- Alphabets and Languages
- Deterministic Finite-State Automata (DFA)
- Regular Languages
- Closure Properties of Regular Languages
- Non-Deterministic Finite-State Automata (NFA)
- e-NFA
- Regular Expressions
- Converting Between Regular Expressions and Finite-State Automata
- The Pumping Lemma for Regular Languages
- Context-Free grammar (CFG) and context-free languages
- Derivations, Parse Trees, Ambiguous Grammars
- Pushdown Automata (PDA)
- PDA Acceptance by Empty Stack and Final State
- Equivalence of Pushdown Automata and Context-Free Grammars
- The Pumping Lemma for Context-Free Languages
- Closure Properties of Context-Free Languages
- Turing Machines (TM)
- The Church-Turing Thesis
- Decidability, the Universal Language, the Halting Problem
- Recursive and Recursively Enumerable Languages
- Rice's Theorem, The Diagonalization Language
Learning Outcomes
- Alphabets, Languages, and Acceptance Problems
- Finite-State Automata (DFA, NFA, and e-NFA Models)
- Regular Languages and their Closure Properties
- Regular Expressions
- Context-Free Grammars and Context-Free Languages
- Pushdown Automata
- Closure properties of Context-Free Languages
- Turing Machines and the Church-Turing Thesis
- The Halting Problem
- Decidability and Undecidability
- Recursive and Recursively Enumerable Languages
- Rice's theorem
Professor Parasara Duggirala's version of the course is more proof-heavy.
Textbook
- Introduction to Automata Theory, Languages, and Computation by Jeffrey Ullman, John Hopcroft, and Rajeev Motwani [Followed by Professor PS Thiagarajan]
- Introduction to the Theory of Computation by Michael Sipser [Followed by Professor Parasara Duggirala and Professor Kevin Sun]
- Elements of the Theory of Computation by Christos Papadimitriou and Harry R. Lewis
Video Playlists
Notes
You can find Professor Kevin Sun's notes here.
Check the Study Strategy.