Teaching
CSC2047: Theory of Computation
Supplementary Resources
The core texts for this module include
-
“Introduction to the Theory of Computation”, Third edition (International edition), Author: Michael Sipser.
-
“The Nature of Computation”, Christopher Moore and Stephan Mertens, Oxford University Press
0. Introduction
- The Turing Tumble and demonstrations of the Turing Tumble
- Module Specification and search for CSC2047.
- Academic & student affairs-> Examinations & Assessment and see “Undergraduate Conceptual Equivalents Scale”
1. Sets and Sequences
- Nice video introducing sets with worked examples. Note we will not be using the # notation for the size of a set.
2. Functions
- Video introducing functions with some worked examples including composite functions.
- Video introducing the concepts of Injective, Surjective, bijective and inverse functions (with examples).
- See also, Introduction to the Theory of Computation (Sipser, 2nd Edition), Pg 7+8 (including examples 0.8, 0.9).
3. Logic
- Notes from Oxford University (Philosophy) on Logic, Propositional and Predicate Calculus with some worked examples. Good guide to deriving propositions and predicates from natural language statements. (Sections 9.4, 10, 15-19 are not necessary for CSC2047 but are interesting topics related to our course material). Document found here.
- Video introducing Propositional Calculus.
- Video illustrating proofs using truth tables.
- Video explaining predicate logic.
4. Graphs and Trees
-
Introduction to the Theory of Computation - Sipser pages 10-12.
-
Introduction to many types of Graphs.
- MIT Mathematics for Computer Science lecture on Graph Theory and Colouring of a graph.
- Overview of trees, traversing trees and how program a problem using a tree.
- Proof of Leonard-Euler Solution to Konigsberg bridge problem.
5. Proofs
- Overview of “IFF” proofs with exercises.
- MIT lecture introducing proofs.
- MIT lecture on proof by induction.
- Overview of proof by contradiction
- Something different: proof by contraposition.
6. Recursion
- Nice introduction to the concept of recursion in terms of programming.
- Some examples of how to define a recursive function from a sequence.
7. Deterministic Finite Automata
-
Solid background introduction to Automata theory can be found in Introduction to the Theory of Computation - Sipser pages 31-40.
-
Lectures introducing Automata theory. See parts 1-5 for DFA.
8 and 9 Nondeterministic Finite Automata
- Explanation on power sets
- Introduction in to Nondeterministic Finite Automata (MIT Prof lecturing).
Below are supplementary resources for the second half of NFA.
- Conversion of NFA to DFA worked example
- Another worked example for converting NFA to DFA (NB. This video uses the notation 2^Q for the power set i.e. P(Q) )
- Introduction to ϵ-NFA and proof of NFA-DFA equivalence found in Introduction to the Theory of Computation - Sipser pages 47-59.
10 and 11 Regular Languages and Regular Expressions
- Background in to the origins of regular languages and the notion of regular expressions.
- Comprehensive lecture on Regular Expressions and constructing NFA/DFA for languages derived from the union/concatenation/star operator applied to a regular language (UC Davis). See 50.34 for proof of RE equivalence to regular languages including the construction of NFA from RE and vice versa.
- Regular Expressions (including proofs and examples) Introduction to the Theory of Computation - Sipser pages 63-76.
12 Non-Regular Langauges
- Introduction to the pumping lemma and examples.
- Lectures on Non-regular languages, examples and the pumping lemma part 1, part 2, part 3, part 4 and part 5 - Remaining lectures in this series are also very useful.
13 Pushdown automata (PDA)
- Clear summary of Pushdown automata (turnstile notation not used in this chapter) found here.
- Introductory lecture on Pushdown automata (note that the notation is different here: the transitions we will be using in this module will be {“input” , “pop from stack” → “push to stack”} and the base symbol in our course will be $ rather than Z as used in this video)
14 Context-free grammars and Context Free Languages
- Introducing the formal definitions of CFGs through CFLs.
- Introducing Grammars through examples and designing CFG - Highly recommeded. (Note e is used instead of 𝜖, we will be using 𝜖 in our module)
- Worked example of deriving CFGs and strings from CFGs.
15 Chomsky Normal Form
- Lecture notes on CNF (see worked example 4.3 for a good explanation of the conversion steps).
- Introduction and reasoning behind CNF and opening lecture (compiler discussion is interesting but beyond the scope of this course.)