Introduction to Theory of Computation

Summer 2013

York University

The course introduces different theoretical models of computers and studies their capabilities and theoretical limitations. Topics covered typically include the following.

- Finite automata and regular expressions; practical applications, e.g., text editors.
- Pushdown automata and context-free grammars; practical applications, e.g., parsing and compilers.
- Turing machines as a general model of computers; introduction to unsolvability: the halting problem.

- August 23: Grades have been submitted. The class average is 65.4%. You can pick assignment 4 and other remaining assignments and tests; they are in a box outside LAS 3052. You can have a look at your final exam on Sept 24 and Sept 26 at 1pm in LAS 3052A. The instuctor is away until Sept 24, but can be contacted by email.
- August 8: Solutions to assignment 3 are here. 16:00 to 18:00 in LAS 2052, where the TA Wendy Ashlock will answer your questions. The instructor is away at a conference until August 12 and he will not have office hours on Aug. 5 and Aug. 8; but he can be contacted by email.
- Here is a final exam from a previous term.
- The
**final exam**is on Monday August 12 09:00-12:30 in CLH K. It covers everthing we have seen this term (including the material discussed at the rescheduled class on July 26). There will be more emphasis on the material we have seen since the second test (i.e. Sipser Chapters 3, 4, and 5), but there will also be questions on the earlier material. - July 30: The
**ninth tutorial**will be on Wed. July 31 17:00-18:30 in LAS 3033. The office hour will be held just before the tutorial from 16:00 to 17:00 in LAS 3052 and there will be no office hour on Thursday August 1. - July 27: Assignment 4 is out; officially it due on August 2 by 17:00 in the dropbox; but it can be submitted without penalty until
**August 7 at 17:00**in the dropbox. - July 23: The deadline for Assignment 3 has been extended; it is now due on
**July 26**at 17:00 in class or in the dropbox. Also note that there is no tutorial this week and that the office hours are at the usual time i.e. on July 25 and 29 17:00-18:00 in LAS 3052. - July 16: There will be a make up lecture on Friday July 26 17:00-20:00 in CLH J to compensate for the July 8 class that had to be cancelled due to the storm and power outage.
- July 16: This week's office hour will be on Wed. July 17 16:00-17:00 (in LAS 3052) instead of the usual Thu. 17:00-18:00 time.
- July 15: Assignment 3 is out; it due on
**July 26**by 17:00 in class or in the dropbox (**extended!**). - The
**eight tutorial**will be on Wed. July 17 17:00-18:30 in LAS 3033. - Solutions to assignment 2 are here.
- A reminder that the
**second test will be on July 15 19:00 to 20:20**. It will cover everything we have seen up to and including Week 8, i.e. Sipser Ch. 0, 1, and 2, excluding Section 2.4. The focus will be on Sections 1.4, 2.1, 2.2, and 2.3. - July 9: Due the storm and power outage, the July 8 class was cancelled. There is a 24h extension for handing in Assignment 2; please submit it in the drop box by 19:00 on July 9.
- The
**seventh tutorial**will be on Wed. July 10 17:00-18:30 in LAS 3033. - The
**sixth tutorial**will be on Wed. July 3 17:00-18:30 in LAS 3033. - June 24: Assignment 2 is out; it due on
**July 8**by 18:45 in the dropbox, or 19:00 in class (extended to July 9 at 19:00). - The
**second test will be on July 15 19:00 to 20:20**. Details on the material covered will be announced later. - The
**fifth tutorial**will be on Wed. June 26 17:00-18:30 in LAS 3033. - The
**fourth tutorial**will be on Wed. June 19 17:00-18:30 in LAS 3033. - June 11: There in no tutorial this week.
- Solutions to assignment 1 are here.
- The instructor office hour on Thu. June 6 is moved to 16:00-17:00 in LAS 3052A so to avoid conflict with the third tutorial.
- The
**third tutorial**will be on Thu. June 6 17:00-18:30 in Ross South 203. - The
**first test will be on June 10 19:00 to 20:20**. It will cover the material in Sipser Ch. 0 and Ch. 1 Sections 1, 2, and 3. Here is a sample first test from a previous term with solutions. - The
**second tutorial**will be on Wed. May 29 17:00-18:30 in LAS 3033. - May 20: Assignment 1 is out; it due on
**June 3**by 18:45 in the dropbox, or 19:00 in class. - May 14: The office hour this week will be on Thursday May 16 16:00-17:00 in LAS 3052 and the TA Paria Mehrani will be there to answer questions. On May 20 the university is closed and there is no class. The first tutorial, led by Paria, will be on Wednesday May 22 17:00-18:30 in LAS 3033; there will also be an office hour there after the tutorial. The instructor office hour on May 23 is cancelled.
- May 9: Readings, suggested exercises, and lecture notes for week 1 have been posted below.
- Classes start May 6.

Prof. Yves Lespérance

Office: LAS 3052A

Tel: 736-2100 ext. 70146

Email: `lesperan "at" cse.yorku.ca`

Monday 19:00 to 22:00 in CLH K (CLH is Curtis Lecture Halls).

Monday and Thursday from 17:00 to 18:00 in LAS 3052A.

Michael Sipser,
*Introduction to the Theory of Computation, Third Edition*
Cengage Learning, 2013.
Book
web site.

If you have the second edition, here is the errata.

The textbook is required; it is available at the York University Bookstore.

General prerequisites; CSE1019 3.00.

Assignements (4 @ 5% each) | 20% |

Tests (2 @ 20% each) | 40% |

Final exam | 40% |

Total | 100% |

It is important that you look at the departmental guidelines on academic honesty. Although you may discuss the general approach to solving a problem with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.

- Week 1 (May 6) Introduction & Mathematical Foundations

*Required Readings:*Sipser Chapter 0.

*Suggested Exercises:*Sipser 0.1 to 0.12.

Lecture transparencies. - Week 2 (May 13) Finite Automata

*Required Readings:*Sipser Section 1.1.

*Suggested Exercises:*Sipser 1.1-1.6, 1.27, 1.31-1.34, 1.48.

Lecture transparencies. - Week 3 (May 20) Victoria Day holiday, no lecture, but there is a tutorial (see What's New above).
- Week 4 (May 27) Finite Automata and Regular Languages

*Required Readings:*Sipser Sections 1.2 to 1.4 inclusive.

*Suggested Exercises:*Sipser 1.7-1.11 (a few parts of each), 1.12, 1.13-1.16, 1.17-1.23, 1.28(b), 1.36, 1.38, 1.39, 1.40, 1.42, 1.44.

Lecture transparencies**(updated!)**. - Week 5 (June 3) The Pumping Lemma and Non-Regular Languages

*Required Readings:*Sipser Section 1.4.

*Suggested Exercises:*Sipser 1.29, 1.30, 1.46, 1.47, 1.49, 1.54, 1.55(a-b), 1.58

Lecture transparencies. - Week 6 (June 10) Context-Free Languages

*Required Readings:*Sipser Sections 2.1 and 2.2.

*Suggested Exercises:*Sipser 2.1, 2.3, 2.4, 2.6, 2.8, 2.9, 2.15, 2.16, 2.25, 2.5, 2.7, 2.10

Lecture transparencies. - Week 7 (June 17) Context-Free Languages and Pushdown Automata

*Required Readings:*Sipser Sections 2.2 and 2.3.

Lecture transparencies. - Week 8 (June 24) Non-Context-Free Languages and CFL Pumping Lemma

*Required Readings:*Sipser Section 2.3.

*Suggested Exercises:*Sipser 2.2, 2.13, 2.30, 2.31, 2.32, 2.35.

Lecture transparencies**(updated!)**. - Week 9 (July 15) Turing Machines and the Church-Turing Thesis

*Required Readings:*Sipser Chapter 3.

*Suggested Exercises:*Sipser 3.1(b), 3.2(a,e), 3.5, 3.7, 3.8(a), 3.10, 3.12, 3.13, 3.15, 3.16, 3.22.

Lecture transparencies**(updated!)**. - Week 10 (July 22 & July 26) Decidability

*Required Readings:*Sipser Chapter 4.

*Suggested Exercises:*Sipser 4.5, 4.6, 4.7

Lecture transparencies part 1 , part 2 . - Week 11 (July 29) Reducibility

*Required Readings:*Sipser Chapter 5 Section 1 pages 215 to 220 as well as all of Section 3.

*Suggested Exercises:*Sipser 5.12, 5.13, 5.4-5.7, 5.9-5.11, 5.22, 5.23

Lecture transparencies**(updated!)**.

Ding-Zhu Du and Ker-I Ko,
*Problem Solving in Automata, Languages, and Complexity*,
Wiley, 2001.

John C. Martin,
*Introduction to Languages and the Theory of Computation*,
McGraw-Hill, 2003.

Daniel Solow,
*How to Read and Do Proofs: An Introduction to Mathematical Thought Processes*,
Wiley,2002.

Jeff Edmonds,
*Abstract Thinking, Intro to the Theory of Computation: SC/COSC
2001 3.0 Lecture Notes, Winter 99-00 Version 0.2*,
available here.