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

Lectures

- Taberet Hall (TBT), Room 070

- Monday 11:30-13:00
- Thursday 13:00-14:30
- Optional review sessions before each term test:

- Friday, February 8, 10:00-11:00, Lamoureux Hall (LMX), Room 242
Friday, March 15, 13:00-14:00, Fauteux Hall (FTX), Room 133Textbook

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.)
- Friday, 12:00-13:00

Exams

- Term Test 1: Monday, February 11

- In class
- Closed book
- Covers material from lectures, textbook, assignments up to page 44 of the class notes for Chapter 7 (up to page 135 of the textbook)
Term Test 2: Monday, March 18

- In class
- Closed book. An appendix will be included with the statements of the pumping lemmas.
- Covers material from lectures, textbook, assignments starting from page 45 of the class notes for Chapter 7 (page 135 of the textbook), up to page 8 of the class notes for Chapter 14 (page 292 of the textbook)
- Final Exam

- Friday, April 26, 14:00-17:00, Fauteux Hall (FTX), Room 147

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-21 Finite Automata, Transition Graphs Chapters 5, 6 January 21-28 Kleene's Theorem, Nondeterministic Finite Automata Chapter 7 January 28-February 14 Finite Automata with Output, Regular Languages Chapters 8, 9 February 14-25 Nonregular Languages, Decidability Chapters 10 (pages 187-196), 11 February 25-March 7 Context-Free Grammars, Grammatical Format Chapters 12, 13 March 7- 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