Theory of Computation

Autumn 2014

The Instructor: Prakash Panangaden.

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

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

- A list of useful facts for the final can be found here.
- Thursday 27th November will be the last class of the term.
- I have slightly changed the order of the lectures. Please check the new schedule. The schedule for homeworks is unaffected.
- Solutions to the mid term are here.

- Lecture Times: Tuesdays and Thursdays 11:30 am to 1:00 pm
- Lecture Place: 232 Leacock
- Office Hours: Tu Th 1:30---3:00
- Office: McConnell (North Wing) 105N

- Maziar Gomkorochi: Office 110 McConnell, Wed 1-2:30 and Thur 9-10:30
- Giulia Alberini: Office 235 McConnell, Wed 2:30-4:00 and Tues 10:00-11:30
- Juan Camilo Gamboa Higuera: Office 403 McConnell, Mon 2:30-4:00 and Fri 1:00-2:30

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. I fixed a typo in the solution of Q5; the regular expression is now (7th Oct) correct. I also fixed a mistake in the solution for Q3.
- Assignment 3. Please note that this was corrected at 3pm on Thursday the 2nd of October. If you downloaded it before that please throw it away and use this copy.
- Solutions to Assignment 3.
- Assignment 4.
- Solutions to Assignment 4.
- Assignment 5.
- Solutions to Assignment 5.
- Assignment 6
- Solutions to Assignment 6.

Supplementary notes are here.

- The basic logic and mathematical structures notes are here. This is essential reading for the first week.
- Notes on converting NFAs to DFAs (handwritten and scanned).
- 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. Read these with care; do not read the part I tell you not to read.
- Notes on duality for automata.
- The statement and the negation of the pumping lemma.
- Notes on labelled transition systems and bisimulation.
- Notes on context-free grammars. Handwritten and scanned.
- Notes on the pumping lemma for context-free languages. Handwritten and scanned.
- Notes on the Coecke-Kasami-Younger for context-free languages. Handwritten and scanned.
- Notes on the lambda calculus.
- Notes on basic computability theory.
- Lecture slides on reduction from 6th November.
- A set that is neither CE nor co-CE. Slightly more detailed notes of a reduction from 6th Nov. In LaTeX format.
- Notes on Rice's theorem (handwritten). From the lecture on 11th November.
- Notes on VALCOMPS. Also from 11th November. Handwritten.
- Validity for first-order logic is undecidable.
- Notes on Goedel numberings and Universality.
- Notes on degrees of undecidability.
- Scanned handwritten notes from the universality lecture. Also includes one sheet on degrees of computability.
- Scanned handwritten notes from the lecture on the recursion theorem. This is required reading.
- Kleene's fixed point theorem. You do not have to read this.

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.