MATH 4P61: Theory of Computation

·  Instructor: Ke Qiu

·  Time and Location: Tu and Th., 5:00-6:30 PM,TH 245

·  Office: J306

·  Office Hours: TBA and by appointment.

General Objectives

Introductions to formal languages, automata, and their relation, and theory of computation. In particular, we will cover the following topics:

 

preliminaries: induction, proofs, sets, countability, Cantor’s theorem, technique of diagonalization;

 

regular sets, languages, and their closure properties, regular, grammars, and finite state machines;

 

context free languages and their closure properties, context-free grammars, push-down automata, normal forms;

 

Turing machines and general introduction to computations: recursive and recursively enumerable languages, (un)decidability, etc.

 

The Chomsky Hierarchy: relations between different classes of languages.

 

Recommended Textbook

Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, 3rd ed., Rajeev Motwani,  and Jeffrey Ullman, Addison-Wesley Publishing Company. A useful link to the book:

http://infolab.stanford.edu/~ullman/ialc.html.

 

The first edition of this book is a classic and one of the best among the many books on this subject.

 

For both the midterm and the final exam, a cheat sheet is allowed. For the ultimate cheat sheet in theoretical computer science, see here.

 

Homework

Assignments are to be handed in by 5:00 PM on the due date specified. Late assignment will be accepted up to one day with a penalty of 50%.

You may discuss assignments with your fellow students. But, please remember not to share solutions. The work you submit must be your own. When submitting an assignment, please follow the general rules for computer science students. Specifically, a standard computer science cover page should be included.

 

Assignment

Out Date

Due Date

Solutions

 

 

 

  

Marking Scheme (tentative)

There will be one midterm (Oct. 26 in class)  and a final exam.

 

 

Assignments (4)

25%

Midterm

25%

Final

50%

Cheating

Cheating and plagiarism as defined in the Academic Integrity section of the Calendar is strictly prohibited. Some forms of cheating are:

  1. copying someone else's answer (including from the internet);
  2. stealing, borrowing, or lending a program listing;
  3. fabricating program output

Cheating in any form will not be tolerated and will be dealt with severely. The penalty is given as follows: Let n be the total mark for an assignment/exam, your mark for this assignment/exam will be -n. A second offence will result in a failing grade for the course. In both cases, the incident will be reported to the department and the registrar's office.