COT 5420 -- Theory of Computation I

Fall 2004

Mondays and Wednesdays, 5:00-6:15, ECS 143

Course Prerequisites



Introduction to the Theory of Computation by Michael Sipser (PWS Publishing, 1997). The author maintains a web site with errata at

"Algebraic Lower Bounds for Finite Automata" by Daniel Cazalis and Geoffrey Smith (manuscript, 2004).

Course Description

In this course, we study a number of mathematical models of computation. Our goal is to understand what can and what cannot be computed using each of these models; this will give us insight into the resources required to solve different problems. One of the most remarkable things that we will learn is that some problems cannot be solved by any computer algorithm. Thus we will see fundamental limits on the power of computers.

Much of what we learn in this class has important practical applicability. For example, regular expressions and context-free grammars are widely used in text-processing applications to specify lexical and syntactic structure. At the same time, it should be recognized that much of the appeal of this subject is purely aesthetic. So to be happy in this course we must try to agree with Keats, at least a little, that

“Beauty is truth, truth beauty,—that is all
Ye know on earth, and all ye need to know.”

The course will be structured as follows:

  1. Mathematical Preliminaries (Chapter 0). Notation, proof by induction, etc.
  2. Regular Languages (Chapter 1). Deterministic and nondeterministic finite automata, regular expressions, the pumping lemma for regular languages, minimal DFAs and NFAs.
  3. Context-Free Languages (Chapter 2). Context-free grammars, pushdown automata, the pumping lemma for context-free languages.
  4. Recursive and Recursively-Enumerable Languages (Chapters 3, 4, and some of 5). Turing machines, undecidability, reducibility.

Problem solving is the heart of this course. What you get out of this course will mostly depend on how much effort you put into solving the homework problems. I will be assigning homework every couple of weeks; also, I encourage you to think about all the exercises and problems in the textbook, whether assigned or not. Finally, I will sometimes designate problems as Bonus Problems; these are challenging problems that I find especially interesting. Solving them earns extra credit.

Homework Groups

I ask that you form groups of size two (or possibly three) for the purpose of submitting homeworks. You should first try to solve the homework problems on your own, and then you should meet with your partner(s) to discuss the solutions that you have found. Then the group should prepare a single write-up of the homework to submit for grading. Having homework groups makes my grading job more manageable, of course, but it also can help you to learn more: you and your partner(s) will often be able to catch one another's errors, and you will often find that your group is able to find cleaner and more elegant solutions than each of you found on your own.


Homework 30%
Midterm Exam 20%
Final Exam 45%
Class Participation 5%
The final exam will be on Wednesday, December 15, from 3:30 to 6:15.

Academic Integrity

I expect you to maintain a high level of academic integrity in this course. Please read FIU's Code of Academic Integrity at For this course, the basic principle to follow is this: the work that you submit should be the result of your group's own effort. You are allowed to consult other books in solving homework problems, or to discuss the problems with other students, but you should cite any such sources that you use. And you must write up your solutions on your own--merely copying answers from the Web, books, or other students is definitely not acceptable.

Finally, I encourage you to make a serious effort to solve the problems on your own before you consult other books or other students. Struggling with different approaches to difficult problems will give you many insights that you won't get by simply reading a beautifully polished answer in a book. (Of course, after you've solved a problem on your own, it's then nice to look at other people's solutions to see how they compare with yours.)


I will grant incompletes only in extreme circumstances, such as medical emergencies.


I expect you to attend class regularly and promptly, and to participate in discussions. Also, please don't be shy about asking questions--if something is unclear to you, it is probably unclear to others as well.

Back to COT 5420 home page.