Theory of Computation

Fall 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.

- The mid term exam is here. Please upload it to the mid term in the assignments tab in myCourses.
- I will hold office hours on
**Thursday 14th October from 10:00 to 11:30 this week only.**I will not hold office hours on Friday this week. From next week onwards my office hours will be Mondays and Fridays 10:00 to 11:30. - I have posted a new version of Assignment 1, there is now an (easier) new question
3. If you wish to stick with the old Question 3, you are free to do so. Please do only
one of these questions
**not both**. - I have made a slight revision of the lecture schedule. Please download an updated
schedule from the link below. The 14th of October is scheduled as a make-up day for the
Fall break, so it is supposed to follow a Monday schedule and there will be no class.
Friday the 15th of October will follow the Tuesday schedule so there will be a
class.
**The due dates for assignments and the midterm date are unaffected.** - On the 30th of September I will be giving a distinguished lecture at the University of Edinburgh, so the class is cancelled for that day.
- On the 8th of October I will be on a plane home from the UK so there will be no office hours that day.

- 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 myCourses under LRS
- Instructor's Office Hours: Wed, Fri 10:00 - 11:30
- Instructor's Office: Zoom
- Discussion group is on myCourses.

- Gulliver Hager : Tuesdays 1:30 - 4:30.
- Rosie Zhao : Fridays 1:00 - 4:00.
- Amirhossein Kazemnajad : Monday: 1:20-2:20, Wednesday, Friday 1:00 - 2:00.
- Kynan Nedellec : Monday, Friday 12:00 - 1:30.
- Yue Wu : Thursdays 1:00 - 4:00.
- Marianick Benoit : Tuesday, Thursday 5:00 - 6:30.
- Maia Darmon : Mondays 5:00 - 6:30 and Fridays 11:30 - 1:00.
- Tyler Kastner : Mondays 2:00 - 5:00.

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 Tuesdays on the dates indicated on the lecture schedule.**

- Assignment 1. I posted a new version on 11th September 2021.
- Solutions to Assignment 1.
- Grading rubric for Assignment 1. This was written by the TAs following my guidelines.
- Assignment 2.
- Solutions to Assignment 2.
- Assignment 3.

- Lecture 1 from 7th January 2021. Basic maths and logic.
- Lecture 2 from 7th September. Deterministic finite automata.
- Lecture 3 from 9th September. Nondeterministic finite automata.
- Lecture 4 from 14th September. Closure properties of regular languages.
- Lecture 5 from 16th September. Algebra of regular expresions.
- Lecture 6 from 21st September. The Pumping Lemma.
- Lecture 7 from 23rd September. More Pumping Lemma examples.
- Lecture 8 on minimization from 28th September.
- Lecture 9 on the Myhill-Nerode theorem from 5th October.
- Lecture 10 on automata learning from 7th October.

- Slides from 2nd september with administrative details.
- The basic logic and mathematical structures notes are here. This is essential reading for the first week.
- Notes on deterministic finite automata (handwritten and scanned). It covers the lecture of 7th September.
- Notes on NFAs
- Notes on NFAs with proofs about conversion of NFAs to DFAs.
- Examples of some NFA constructions by Ralph Sarkis, former TA now doing a PhD in Lyon, France. Thanks Ralph!
- An example showing exponential blow up when converting an NFA to a DFA.
- Closure properties of regular languages.
- 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.
- The statement and the negation of the pumping lemma.
- Handwritten examples showing how to use the pumping lemma.
- Notes on minimization of DFA. Handwritten and scanned.
- Notes on algorithms for finite automata and regular languages.
- Notes on the Myhill-Nerode Theorem.
- Notes on automata learning by Ariella Smofsky.

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.