· Instructor: Ke Qiu
· Time and Location: Tu and Th., 5:006:30 PM,TH 245
· Office: J306
· Office Hours: TBA and by appointment.
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, contextfree grammars, pushdown 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.
Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, 3^{rd} ed., Rajeev Motwani, and Jeffrey Ullman, AddisonWesley 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.
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 







There will be one midterm (Oct. 26 in class) and a final exam.
Assignments (4) 
25% 
Midterm 
25% 
Final 
50% 
Cheating and plagiarism as defined in the Academic Integrity section of the Calendar is strictly prohibited. Some forms of cheating are:
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.