COT 5420 -- Theory of Computation I
Mondays and Wednesdays, 5:00-6:15, ECS 143
- MAD 3512 (Formal Languages and Automata)
- Geoffrey Smith
- Office: ECS 320
- Telephone: 305 348-6037
- E-mail: smithg @ cs.fiu.edu
- Office Hours: Mondays and Wednesdays, 3:30 -- 4:45
I'll usually be happy to meet at other times.
Send e-mail, call, or drop by.
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).
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
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:
- Mathematical Preliminaries (Chapter 0).
Notation, proof by induction, etc.
- Regular Languages (Chapter 1).
Deterministic and nondeterministic finite automata, regular expressions,
the pumping lemma for regular languages, minimal DFAs and NFAs.
- Context-Free Languages (Chapter 2).
Context-free grammars, pushdown automata, the pumping lemma for context-free
- 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.
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.
The final exam will be on Wednesday, December 15, from 3:30 to 6:15.
|Midterm Exam ||20%|
|Final Exam ||45%|
|Class Participation|| 5%|
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.
COT 5420 home page.