Winter 2019

(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

- Thursday, 9:30-11:30 (
except January 17)

Lectures

- Hagen Hall (HGN), Room 302
- Monday 11:30-13:00
- Thursday 13:00-14:30
No class January 14 and 17Textbook

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, 20%
- 2 Term Tests, 30% (will take place during class time, closed book)
- Final Exam, 50%

- There will be approximately 7 or 8 assignments.

Assignments

- All assignments will be posted directly on Virtual Campus.
Handing in assignments: Assignments must be submitted either by putting them in AssignmentBox 11on the first floor of the SITE building, or electronically using your Virtual Campus account.

- If you hand in a hard copy, you must staple the pages of your assignment together, and include your Name, Student Number, Course number, and Assignment number on every page.
- If you hand in an electronic copy, include your Name, Student Number, Course number, and Assignment number in every file.
Late policy:For full credit, the assignment must be handed in by the due date and time. Late assignments must be submitted on Virtual Campus. 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.
TA: Abdorrahim Bahrami (abahr010@uottawa.ca)

- Office Hours:

- CBY Room B405 (Please knock on the door.)
- Times to be announced.

Exams

- Term Test 1: Monday, February 11
- Term Test 2: Monday, March 18
- 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 Date Introduction, Languages, Recursive Definitions Chapters 1, 2, 3 January 7-10 Regular Expressions Chapter 4 January 10- Finite Automata, Transition Graphs Chapters 5, 6 Kleene's Theorem, Nondeterministic Finite Automata Chapter 7 Finite Automata with Output, Regular Languages Chapters 8, 9 Nonregular Languages, Decidability Chapters 10 (pages 187-196), 11 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