Theory of Computation

Winter 2021

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.

- I have given a
**24 hour extension**for Assignment 6. It is now due on the 9th of April at 6pm. - I have slightly revised the notes on first order logic at 10:50am on the 8th of April 2021.
- The last quiz will be on the 9th-10th of April. This is because the 2nd is Good Friday and is a national holiday.
- I corrected a typo in the solution of Q5 on A3: I had the membership statements backwards. The correct version can be downloaded now.
- I have made a slight change to the lecture schedule. I will start computability theory on the 11th of March. You can download the latest schedule below.
- Neither the TAs nor I will be holding office hours during the Winter Break 1-5 March 2021.
- Please note the slight change in James Bodzay's office hours.
- The midterm results are now entered and there should be a breakdown of marks under "Feedback". The midterm grading scheme is here. The midterm solutions are here.
- The midterm exam is here. Please download the questions and submit your answers through the Assignments tab on myCourses. Please use a single pdf file. You must submit by 8am Saturday the 13th of February.
- There is an important change in the course schedule. Quiz 5 has been postponed to the 8-9th of April because the 2nd is a National holiday. You can download an up-to-date schedule from the link below.
- There is a slight change in the lecture schedule. I will do the pumping lemma before minimization. You can download an up-to-date schedule from the link below.
- A minor clarification for Q2 on assihnment 1: I have put in some extra parentheses to head off any possible ambiguity in interpreting the definition. I thank Cameron (Sam) Cherif for gently pointing out the possibility that this could be confusing. A new version of the assignment has been posted.
- Quizzes are now scheduled to be taken over a
**24-hour**period rather than a 16 hour period. The quiz period will start on Friday morning and end on Saturday morning. - Someone once said on a Facebook post that 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:35 to 12:55.
- Lectures are on Zoom and are recorded. The link is on myCourses.
- Lecture recordings will be linked on Zoom
- Instructor's Office Hours: Tue, Th 1:30---3:00
- Instructor's Office: Zoom
- Discussion group is on myCourses.

- Johanna Schwartzentruber Mon Wed 10:30 am - 11:30 am.
- James Bodzay Mon 3:00 pm - 5:00 pm.
- Florestan Brunck Fri 10:00 am - 12:00 noon and Tue 3:00 pm - 4:00 pm.
- Molly Sun Wed 8:30 am - 10:30 am.
- Roland RiachiWed 2:00 pm - 4:00 pm.
- Lin Xiao Zheng Tue 2:00 pm - 4:00 pm.
- Yue Wu Mon 2:30
**am**- 4:30**am**. This is for the benefit of people in other time zones.

Quizzes are to be completed through myCourses. The dates are shown on the schedule. There will be 5 of them and they are scheduled to be on Fridays extending to the following Saturday morning. You will be able to access the quiz starting at 7:00am and it will close at 7:00am the next day. You will have 1 hour to complete the quiz. The quiz will close at the designated time regardless of when you start. If you want the full hour please start at least 1 hour before the end time.

- Quiz 1 answers from 15-16th January.
- Quiz 2 answers from 29-30th January.
- Quiz 3 answers from 26-27th February.
- Quiz 4 answers from 19-20th March.
- Quiz 5 answers from 9-10th April.

Assignments and their solutions will be posted here. They will be
in pdf format. Please submit solutions through myCourses. You are allowed
to submit ** one file only**. You can resubmit until the deadline; the
older file will be deleted. ** Please use pdf for submission.** We will
not accept doc files, or jpegs. ** The deadline is 5pm on Thursdays.**

- Assignment 1
- Solutions to Assignment 1.
- Assignment 2.
- Solutions to Assignment 2.
- Grading guide to Assignment 2.
- Assignment 3. I used a slightly different notation for the Myhill-Nerode equivalence relation in my notes and in Q5 of Assignment 3. I updated this file on the 9th of February.
- Solutions to Assignment 3.
- Solutions to Assignment 3 with the remarks for the graders included.
- Marking scheme for Assignment 3 prepared by the graders.
- Assignment 4.
- Solutions to Assignment 4.
- Solutions and grading guide for Assignment 4.
- TAs' grading rubric for Assignment 4.
- Assignment 5.
- Solutions to Assignment 5. These were updated on the 27th of March. There was a mistake in my previous solution for Q2 but it has been corrected. If you downloaded the solutions before Saturday please discard it and download the new copy. The error was pointed out by Omar Mohamed Wagih Sadek, thanks Omar!
- Solutions to Assignment 5 with comments for the graders.
- TAs' grading rubric for Assignment 5.
- Assignment 6.
- Solutions to Assignment 6.
- Solutions to Assignment 6 with remarks for graders.
- TAs' grading rubric for Assignment 6.

- Lecture 1 from 7th January. Basic maths and logic.
- Lecture 1 from 7th January. Version with a reduced file size for easier downloads.
- Lecture 2 from 12th January. Deterministic finite automata.
- Lecture 2 from 12th January. Version with a reduced file size for easier downloads.
- Lecture 3 from 14th January. Nondeterministic finite automata.
- Lecture 3 from 14th January. Version with a reduced file size for easier downloads.
- Lecture 4 from 19th January. Regular expresions.
- Lecture 4 from 19th January. Version with a reduced file size for easier downloads.
- Lecture 5 from 21st January. Algebra of regular expresions; closure properties of regular languages.
- Lecture 5 from 21st January. Version with a reduced file size for easier downloads.
- Lecture 6 from 26th January. The pumping Lemma.
- Lecture 6 from 26th January. Version with a reduced file size for easier downloads.
- Lecture 7 from 28th January. More Pumping Lemma examples.
- Lecture 7 from 28th January. Version with a reduced file size for easier downloads.
- Lecture 8 on minimization from 2nd February.
- Lecture 8 from 2nd February. Version with a reduced file size for easier downloads.
- Lecture 9 on the Myhill-Nerode theorem from 4th February.
- Lecture 9 from 4th February. Version with a reduced file size for easier downloads.
- Lecture 10 on context-free languages from 16th February.
- Lecture 10 from 16th February. Version with a reduced file size for easier downloads.
- Lecture 11 on context-free languages from 18th February.
- Lecture 11 from 18th February. Version with a reduced file size for easier downloads.
- Lecture 12 on pushdown automata from 23rd February.
- Lecture 12 from 23rd February. Version with a reduced file size for easier downloads.
- Lecture 13 on pushdown automata and algorithms for CFLs from 25th February.
- Lecture 13 from 25th February. Version with a reduced file size for easier downloads.
- Lecture 14 on the pumping lemma for context-free languages from 9th March.
- Lecture 14 from 9th March. Version with a reduced file size for easier downloads.
- Lecture 15 Introduction to Computability: 11th March.
- Lecture 15 from 11th March. Version with a reduced file size for easier downloads.
- Lecture 16 Models of Computation including Turing machines: 16th March.
- Lecture 16 from 16th March. Version with a reduced file size for easier downloads.
- Lecture 17 Computability Theory : 18th March.
- Lecture 17 from 18th March. Version with a reduced file size for easier downloads.
- Lecture 18 Reductions - I : 23rd March.
- Lecture 18 from 23rd March. Version with a reduced file size for easier downloads.
- Lecture 19 Reductions - II : 25th March.
- Lecture 19 from 25th March. Version with a reduced file size for easier downloads.
- Lecture 20 Valid Computations : 30th March.
- Lecture 20 from 30th March. Version with a reduced file size for easier downloads.
- Lecture 21 The Post Correspondence Problem : 1st April.
- Lecture 21 from 1st April. Version with a reduced file size for easier downloads.
- Lecture 22 First-order Logic : 6th April.
- Lecture 22 from 6th April. Version with a reduced file size for easier downloads.
- Lecture 23 Last topics from computability: 8th April.
- Lecture 23 from 8th April. Version with a reduced file size for easier downloads.
- Lecture from 13th April. Last class, review for the final exam.

- Slides from 7th January with administrative details.
- The basic logic and mathematical structures notes are here. This is essential reading for the first week.
- Lecture on deterministic finite automata (DFA) from 12th January.
- Notes on NFAs from 14th January.
- Notes on NFAs with proofs about conversion of NFAs to DFAs. From 14th January.
- Examples of some NFA constructions by Ralph. Thanks Ralph!
- 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. - Handwritten notes on the pumping lemma.
- Handwritten notes on the pumping lemma. File size reduced, otherwise the same as the above.
- The statement and the negation of the pumping lemma.
- Handwritten examples showing how to use the pumping lemma.
- Handwritten examples showing how to use the pumping lemma. Reduced file size.
- Examples of shuffling. I wrote a little program to compute shuffles and ran it on two small examples.
- Notes on minimization of DFA. Handwritten and scanned.
- Notes on the Myhill-Nerode Theorem.
- Notes on context-free grammars. Handwritten and scanned.
- An example proof about context-free languages.
- Notes on pushdown automata. Handwritten and scanned.
- Notes on an algorithm to test
whether the language generated by a CFG is empty. You should know how
this algorithm works but you should
**not**memorize it or practice executing is quickly. You might be expected to use it as a building block of another algorithm. - Notes on Chomsky Normal Form . You should
be aware what CNF means and that there is an algorithm to covert a CFG to
CNF but you need not learn the details. I will
**never ask you to excute an algorithm on an exam.** - Notes on the Coecke-Kasami-Younger algorithm for context-free languages. Handwritten and scanned. You should know that this algorithm exists but you need not memorize it or be familiar with the details.
- Note showing that the complement of the language of repeated words is a CFL by describing a PDA.
- Notes on parsing. This is for your information only. Parsing is a major topic and to learn it properly you should take COMP 520.
- Notes on the pumping lemma for context-free languages. Handwritten and scanned.
- The Halting Problem. theory.
- The definition of a Turing machine. This includes the same example as the next handout.
- An example of a Turing machine. This one recognizes a non-CFL.
- A bijection between
**N**and**N**x**N**. You don't need this level of detail for anything in the homework but some of you seem to be suspicious about believing anything without explicit proof. - Notes on basic computability
- 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).
- Notes on VALCOMPS.
- Notes on the Post Correspondence Problem. Here is a picture showing how to finish off the match.
- Validity for first-order logic is undecidable. Revised on the 8th of April at 10:50am.
- Scanned handwritten notes from the lecture on the recursion theorem. You will not be tested on this topic.
- Notes on degrees of undecidability. This is optional; you will not be tested on it.

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.

Chaque étudiant a le droit de soumettre en français ou en anglais tout travail écrit.

The Instructor: Prakash Panangaden at the end of the course.