Theory of Computation

Autumn 2015

The Instructor: Prakash Panangaden (during office hours)

**E-mail:** prakash@cs.mcgill.ca

Announcements about the course will be posted here. Long handouts will be in
pdf format.

- I guess people would rather see me before the last class than
after. Accordingly, I have shifted my office hours from Thursday after
class to Wednesday 11:00 to 1:00. These will be my
**last office hours**of the term. I will hold office hours in the week of the final on Monday 14th December from 12 to 2. There will be no office hours during the week of Dec 7-11. - The mid term solution are here.
- Someone recently said COMP 330 is interesting but you will only see things that have no applications. Please check the following link. for dissenting opinions.

- Lecture Times: Tuesdays and Thursdays 11:30 am to 1:00 pm
- Lecture Place: 112 Rutherford
- Instructor's Office Hours: Mon 11:30---1:00 and Th 1:30---3:00
- Instructor's Office: McConnell (North Wing) 105N
- Discussion groups are on myCourses and Facebook.

- Giulia Alberini: 235 McConnell Wed 8:30--10:30
- Harrison Humphrey: 110 McConnell Fri 1:00--3:00
- Tricia Olson: Trottier TA room, Mon 10:00 -- 11:30, Wed 10:30 -- 1:00

- Pascale Gourdeau : 112 McConnell Tue 9:00--11:00 (Tomlinson undergraduate mentor)

Assignments and their solutions will be posted here. They will be in pdf format.

- Assignment 1
- Solutions to Assignment 1.
- Assignment 2.
- Solutions to Assignment 2.
- Assignment 3.
- Solutions to Assignment 3.
- Assignment 4.
- Solutions to Assignment 4.
- Assignment 5.
- Solutions to Assignment 5.
- Assignment 6

Supplementary notes are here.

- The basic logic and mathematical structures notes are here. This is essential reading for the first week.
- Lecture on deterministic finite automata (DFA) from 10th Sept.
- Notes on converting NFAs to DFAs (handwritten and scanned) from 15th Sept.
- An example showing exponential blow up when converting an NFA to a DFA.
- Notes on constructing an NFA to recognize the language defined by a regular expression. (handwritten and scanned).
- Notes on extracting a regular expression from a DFA (handwritten and scanned).
- Notes on the algebra of regular
expressions, (handwritten and scanned). Ignore the
*Lecture 7*at the top of the page. - Notes on minimization of DFA. Handwritten and scanned.
- Notes on the Myhill-Nerode Theorem.
- Notes on Brzozowski's algorithm.
- Notes on labelled transition systems and bisimulation.
- The statement and the negation of the pumping lemma.
- Notes on context-free grammars. Handwritten and scanned.
- Basic facts about context-free languages.
- Notes on the pumping lemma for context-free languages. Handwritten and scanned.
- Notes on the Coecke-Kasami-Younger algorithm for context-free languages. Handwritten and scanned.
- Notes on basic computability theory.
- Notes on reductions.
- Handwritten notes on reduction.
- A set that is neither CE nor co-CE. In LaTeX format.
- Notes on Rice's theorem (handwritten). From the lecture on 12th November.
- Notes on VALCOMPS. From 19th November. Handwritten. These were blown away in a breeze so this is the only copy of these notes.
- Notes on degrees of undecidability.
- Validity for first-order logic is undecidable.

McGill University values academic integrity. Therefore all students
must understand the meaning and consequences of cheating, plagiarism and
other academic offenses under the Code of Student Conduct and Disciplinary
Procedures ( see
http://www/mcgill.ca/integrity for more information). Most
importantly, work submitted for this course must represent your own
efforts. Copying assignments or tests from any source, completely or
partially, or allowing others to copy your work, will not be tolerated.

The Instructor when you drop in while he is having a meeting.