Instructor:
Xinhua Zhuang
313 EBW
Department of Computer Engineering and Computer Science
University of MissouriColumbia
Columbia, MO 65211
Phone: 8822382
Email: zhuang@cecs.missouri.edu
Office Hours: Tuesday and Thursday, 9:15am  10:00am, or by appointment
WWW: http://meru.cecs.missouri.edu/courses/cecs341
Objectives:
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
include:
 Finite automata and regular languages
 Deterministic and nondeterministic computations
 Contextfree grammars, languages, and pushdown automata
 Turing machines
 Undecidable problems
 Computational complexity, NPcompleteness
Prerequisites:
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, AddisonWesley, 1979. (Recommended)
Expected Work:
Reading; homeworks (problem sets); one midterm exam and one final exam.
Grading Policy:
 Homeworks: 40 %
 Midterm Examination: 25 %
 Final Examination: 35 %
The midterm exam will be held during one of the normal class periods. The Final will be comprehensive,
covering the entire semester.
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
(measured noontonoon).
Assignments will not be accepted three days after the due date.
Collaboration
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
own.
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.
Lecture Notes
These lecture notes are in pdf format. You will need Adobe Acrobat Reader to read them.
Theory of Computation
Mathematical Preliminaries
Mathematical Preliminaries
Finite Automata
Regular Languages
Nondeterminism
Regular Languages
Regular Expressions
Pumping Lemma
Summary of Finite Automata
ContextFree Languages
Review
Pushdown Automata
Pushdown Automata
PDA: Equivalence with CFG
Pumping Lemma for CFLs
Properties of CFLs
Universal Models of Computation
Turing Machine
Variants of Turing Machines
Notation of Algorithm
Complexity Theory
The Class P
The Class NP
NPCompleteness
CECS Multimedia Communications and Visualization Laboratory