Introduction to Theory of Computation (COMP 3803)
Office: Herzberg Building 5125C
Lectures: Tuesday and Thursday, 11:35-12:55,
Tory Building 342
Office hours: Wednesday 9-11
- TA's office hours will be held in Herzberg Building 5356
- Darryl Hill
Office hours: Thursday 1-3
- Yunkai Wang
Office hours: Tuesday 1-3
Theoretical aspects of computer science.
Topics covered include:
Formal languages and automata theory (regular languages, finite
automata, context-free languages, pushdown automata),
computability theory (Turing machines, Church-Turing Thesis,
decidability, Halting Problem).
- Assignment 1: posted January 17, due January 31
- Assignment 2: posted January 31, due February 14
- Midterm: Thursday February 28
- Assignment 3: posted March 7, due March 21
- Assignment 4: posted March 21, due April 4
- Final exam: TBA
- Assignments: 25%
- Midterm: 25%
- Final exam: 50%
- Late assignments will not be accepted.
- Real computer scientists use
LaTeX to type
their solutions. In case you want to learn LaTeX,
here is a tutorial.
- You can use the freely available
drawing editor to make figures.
- Each assignment must be submitted as one single PDF file through
- You can type your solutions, or write them by hand and scan them
(for example, using a scan app on your phone or using a real
- Instructions on how to submit your assignment can be found
- Assignment 1 is due Thursday January 31, before 11:55pm.
- Here is Assignment 1 as a
- Here is the LaTeX file,
here are the figures.
- Information about the midterm will be posted here.
- Information about the final exam will be posted here.
What was done in class:
- January 8: Overview; Sections 1.1 and 2.1; example on page 23.
(Take a quick look at Sections 1.2 and 1.3.)
- January 10: Deterministic finite automata: definition and examples
- January 15: Union of two regular languages is regular,
regular operations: union, concatenation, and star (Section 2.3);
introduction to NFAs (Section 2.4.1).
- January 17: Nondeterministic finite automata (Sections 2.4.1, 2.4.2,
and 2.4.3), definition of nondeterministic finite automaton
(Section 2.4.4); equivalence of deterministic and nondeterministic
finite automata without epsilon-transitions (Section 2.5).
- January 22: Equivalence of deterministic and nondeterministic
finite automata (Section 2.5); closure under the regular operations
(Section 2.6); Exercise 2.18.
- January 24: Regular expressions (Section 2.7); how to convert a
regular expression to an NFA (Section 2.8.1).
- January 29: How to convert a DFA to a regular expression
- January 31: The Pumping Lemma for regular languages (Section 2.9).
- February 5: Proof of the Pumping Lemma for regular languages
(Section 2.9); definition of context-free grammars (Section 3.1);
properly nested parentheses (Section 3.2.1).
- February 7: Examples of context-free grammars (Section 3.2);
converting a DFA to a CFG, every regular language is context-free
- February 12: Chomsky Normal Form; converting a context-free grammar
to Chomsky Normal Form (Section 3.4).
- February 14: Deterministic pushdown automata (Sections 3.5, 3.6.1,
- February 18-22: Winter break.
- February 26: Nondeterministic pushdown automata (Section 3.6.3);
converting a context-free grammar to a nondeterministic pushdown
automaton (Section 3.7).
- February 28: Midterm, in class.
- March 5: Pumping lemma for context-free languages (Section 3.8);
proof of the pumping lemma (Section 3.8.1); first example in
- March 7: Examples of languages that are not context-free
- March 12: Solutions midterm; the intersection of two context-free
languages may not be context-free; the intersection of a context-free
language and a regular language is context-free.
- March 14:
machines (Section 4.1);
examples of Turing machines (Sections 4.2.1 and 4.2.2).
- March 19: Example of a Turing machine (Section 4.2.5); equivalence
of multi-tape Turing machines and single-tape Turing machines
(Section 4.3). What is an algorithm? Church-Turing Thesis
- March 21: Definition of a language being decidable (Section 5.1);
the languages A_DFA, A_NFA, and A_CFG are decidable; every
context-free language is decidable (Sections 5.1.1, 5.1.2, 5.1.3);
the Halting Problem is undecidable (Sections 5.1.5 and 5.2.1).
- March 26: Countable sets, the real numbers are not countable
(Section 5.2); the language A_TM is undecidable (Section 5.1.4);
introduction to Rice's Theorem (Section 5.3).
- March 28: Rice's Theorem (Section 5.3).
- April 2: Enumerable languages (Sections 5.4 and 5.5).
- April 4: Language A is decidable if and only if both A and its
complement are enumerable (Section 5.7); Halt is enumerable, but its
complement is not enumerable (Section 5.7); both EQ_TM and its
complement are not enumerable (Section 5.8); the set of all
enumerable languages is countable (Section 5.6.1); the set of all
languages is not countable (Section 5.6.2).
- April 9: Review. Read Chapter 7.