Department of Computer Engineering and Computer Science
University of Missouri-Columbia
Columbia, MO 65211
Office Hours: Tuesday and Thursday, 9:15am - 10:00am, or by appointment
This course introduces the fundamental mathematical models of computation.
We study both the inherent capabilities and limitations
of these computational models as well as their
relationships with formal languages.
Topics to be covered
- Finite automata and regular languages
- Deterministic and nondeterministic computations
- Context-free grammars, languages, and pushdown automata
- Turing machines
- Undecidable problems
- Computational complexity, NP-completeness
Texts (Reserved in Engineering Library)
Introduction to the Theory of Computation, by Michael Sipser, PWS publishing Co., 1997. (Required)
- Hopcroft and Ullman,
Introduction to automata theory, languages, and computation, by Hopcroft and Ullman, Addison-Wesley, 1979. (Recommended)
Reading; homeworks (problem sets); one midterm exam and one final exam.
The midterm exam will be held during one of the normal class periods. The Final will be comprehensive,
covering the entire semester.
- Homeworks: 40 %
- Midterm Examination: 25 %
- Final Examination: 35 %
Homework Submission Policy
Homeworks will be accepted by the end of class on the day it is due.
Your homework should be neat, legible, and identified with your name and the assignment number.
It should be comprehensible: clear, concise, well
organized, complete, and most of all, well documented.
Staple all sheets together before turning them in.
Penalties for Lateness
Every homework assignment will list a due date for full credit.
Late assignments will lose 10% of the maximum score per day
Assignments will not be accepted three days after the due date.
You may assist each other to understand the material that
we are teaching.
You may discuss homework assignments with other
students at a general level. But all problem set solutions
and testing must be done entirely on your
Penalties for Cheating
Academic honesty is fundamental to the activities and principles of a
university. Cheating will not be tolerated and will be severely
punished. For the first offense, you will receive a substantial
negative score for that assignment. Any additional offense may result
in failure for the course.
These lecture notes are in pdf format. You will need Adobe Acrobat Reader to read them.
Theory of Computation
Summary of Finite Automata
PDA: Equivalence with CFG
Pumping Lemma for CFLs
Properties of CFLs
Universal Models of Computation
Variants of Turing Machines
Notation of Algorithm
The Class P
The Class NP
CECS Multimedia Communications and Visualization Laboratory