Regular languages, finite automata, transition graphs, Kleene's theorem. Finite automata with output. Context-free languages, derivation trees, normal form grammars, pumping lemma, pushdown automata, determinism. Decidability. Recursively enumerable languages, Turing machines, the halting problem. Prerequisites: CSI2101 or MAT2143.
Course Outline
Professor-
Dr. Amy Felty
SITE 5-068
afelty@uottawa.ca
Office Hours
- Thursday, 16:00-18:00, Note new time.
- Starting Thursday, March 26, office hours will be online. See Brightspace for the link.
Correctors
- Hieu Nguyen, hnguy028@uottawa.ca
- Wenbin Zhang, wzhan133@uottawa.ca
Lectures
- Taberet Hall (TBT), Room 070
- Monday 11:30-12:50
- Thursday 13:00-14:20
- Lectures are now online. Click here to see a list of class links for online classes (via Adobe Connect) at the University of Ottawa.
- Introduction to Computer Theory, Daniel Cohen, Wiley, 2nd edition, available at the university bookstore.
- Two or three copies are available on reserve at the Morisset Library.
- Some errors in the textbook are described in Section 5.2 of this document.
Evaluation
- Assignments, 25%
- Midterm Exam, 25% (February 27 during class, closed book)
- Final Exam, 50%
- There will be approximately 7 or 8 assignments.
Assignments
- All assignments will be posted directly on Brightspace.
- Handing in assignments: Assignments must be submitted electronically using your Brightspace account. The option to submit hard copies to the assignment box is no longer available.
- Late policy: For full credit, the assignment must be handed in by the due date and time. Late assignments must be submitted on Brightspace. Late assignments in the assignment box will not be accepted. Any late assignments handed in up to 2 days after the due date will have a deduction of 25%. After that, any late assignments handed in up to 4 days after the due date will have a deduction of 50%. No assignments after that will be accepted.
- Each student is required to do each assignment individually. Please see the policy on plagiarism.
Exams
- Midterm: Thursday, February 27
- In class
- Closed book
- Covers material from lectures up to the first pumping lemma (course notes for Chapter 10 to end of page 7), textbook (up to end of examples on page 194), and assignments
- There will be an appendix on the exam with the statement of the first pumping lemma.
- Final Exam
- Friday, April 24, 19:00-22:00
- Covers material from lectures, textbook, assignments up to the end of Chapter 17
- Open book
- Online
- Click here for information on preparing your computer for online exams and for what to do if you encounter technical issues during the exam.
Other Links
Course Outline
Details will be filled in as the term progresses.
| Topic | Reading | Date |
|---|---|---|
| Introduction, Languages, Recursive Definitions | Chapters 1, 2, 3 | January 6-9 |
| Regular Expressions | Chapter 4 | January 9-13 |
| Finite Automata, Transition Graphs | Chapters 5, 6 | January 13-20 |
| Kleene's Theorem, Nondeterministic Finite Automata | Chapter 7 | January 20-30 |
| Finite Automata with Output, Regular Languages | Chapters 8, 9 | January 30-February 3 |
| Nonregular Languages, Decidability | Chapters 10 (pages 187-196), 11 | February 3-March 2 |
| Context-Free Grammars, Grammatical Format | Chapters 12, 13 | March 2-12 |
| Pushdown Automata, Context-Free Grammars = Pushdown Automata | Chapters 14, 15 (pages 318-327) | March 12-19 |
| Non-Context-Free Languages | Chapter 16 | March 19-23 |
| Turing Machines | Chapter 19 | March 23-26 |
| Recursively Enumerable Languages | Chapter 23 | March 26-30 |
| Context-Free Languages | Chapter 17 (pages 376-394, not including proof of Theorem 41) | March 30 |
| Decidability, Parsing | Chapter 18 (pages 402-406 and 415-423) | March 30-April 2 |
