Winter 2017

(3 hours of lecture per week, 3 credits)

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 OutlineProfessorDr. Amy Felty

SITE 5-068

afelty@uottawa.ca

Office Hours

- Tuesday, 13:30-15:30

Lectures

- Monday 11:30-13:00, LMX 390
- Thursday 13:00-14:30, LMX 390
Textbook

Introduction to Computer Theory, Daniel Cohen, Wiley, 2nd edition, available at the university bookstore.- Two 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, 20% (late assignments not accepted)
- 2 Term Tests, 30% (will take place during class time, closed book)
- Final Exam, 50%

- There will be approximately 7 or 8 assignments.

Assignments

- Information about assignments is available here.
- Please see the policy on plagiarism.

Exams

- Term Test 1: Thursday, February 9

- In class
- Closed book
- Covers material from lectures, textbook, assignments up to the end of Chapter 7
- Term Test 2: Thursday, March 16

- In class
- Closed book
- Final Exam: during exam period

CopyrightAll materials prepared by the course professor, including course notes, assignments, sample solutions, and exam papers, are copyright. Copying or scanning them or posting them on a website is therefore a violation of copyright and is illegal.

Other Links

Course OutlineDetails will be filled in as the term progresses.

Topic Reading Lecture Notes Date Introduction, Languages, Recursive Definitions Chapters 1, 2, 3 Chapters 1 and 2,

Chapter 3January 9-12 Regular Expressions Chapter 4 Chapter 4 January 12-16 Finite Automata, Transition Graphs Chapters 5, 6 Chapter 5,

Chapter 6January 16-23 Kleene's Theorem, Nondeterministic Finite Automata Chapter 7 Chapter 7 January 23-February 6 Finite Automata with Output, Regular Languages Chapters 8, 9 Chapter 8,

Chapter 9February 13-16 Nonregular Languages, Decidability Chapters 10 (pages 187-196), 11 Chapter 10,

Chapter 11February 16- Context-Free Grammars, Grammatical Format Chapters 12, 13 Pushdown Automata, Context-Free Grammars = Pushdown Automata Chapters 14, 15 (pages 318-327) Non-Context-Free Languages, Context-Free Languages Chapters 16, 17 Decidability, Parsing, Turing Machines Chapters 18 (pages 402-410 and 415-423), 19 Recursively Enumerable Languages Chapter 23