Dr. Jody Paul

Computer Science Education
Theory of Computation

Course Information

Title: Introduction to the Theory of Computation
Institution: Metropolitan State College of Denver
Semester: Fall 2003 (August 18 - December 13)
ID, Section [CRN]: CSI 3240, Section 1 [54773]
Meeting Times:

Mondays and Wednesdays, 6:00 PM - 6:50 PM


Science 112

Course Website: http://www.jodypaul.com/cs/theory
Discussion Board: http://cs.mscd.edu/~discus
Instructor: Dr. Jody Paul (schedule)
E-mail: jody@computer.org
Office: Science 133C
Office Hours:

Mondays/Wednesdays 6:50PM - 7:50PM
Tuesdays/Thursdays, 1:00PM - 2:00PM
Thursdays 9:30PM - 10:30PM
Other days and times by appointment

Campus Mail: Campus Box 38


Course Description:

This course explores language theory and computability. Language theory includes: regular expressions, regular languages, finite automata (deterministic and non-deterministic), context-free languages, pushdown automata, and language grammars. Computability includes: Turing machines and their computing power, unsolvable problems, and intractable problems (NP-Completeness).
Prerequisites: CSI 3050 and MTH 3100 with grades of C or better, or permission of instructor.

Course Objectives:

Upon completion of this course the you should be able to:
  • Determine the language represented by a regular expression
  • Create a regular expression from a language description
  • Construct a deterministic finite automaton accepting a given language
  • For a given finite automaton (deterministic or nondeterministic) determine if a string is accepted
  • Draw a state diagram for a finite automaton (deterministic or nondeterministic) that accepts a given language
  • For a given finite automaton (deterministic or nondeterministic) find a minimum-state equivalent deterministic finite automaton
  • Use a grammar to generate or accept a string
  • For a given grammar give the derivation(s) of a specified string and draw the corresponding parse tree(s)
  • Construct a context-free grammar for a language
  • Construct a pushdown automaton that accepts a given language
  • Show that a specific language is context-free
  • Trace the computation for a specified Turing machine
  • Create a Turing machine to solve a specified problem
  • Determine whether a problem about Turing machines is solvable or undecidable
  • Arrange classes of languages in order of increasing generality
  • Discuss relative computational power of language recognizers


Image of Book Cover - Data Structures and Algorithms in Java / Link to 

Introduction to the Theory of Computation
  [Tattered Cover][Amazon]
by Michael Sipser
PWS Publishing Company, New York (1997)
ISBN 0-53494-728-X
Textbook Errata

You must have World Wide Web access and an e-mail account. Note that you receive an e-mail account and Internet access by virtue of being a student at MSCD (see: http://www.mscd.edu).

Grading Policy:

Your final course grade is determined by combining your grades on assignments and exams. You are guaranteed a grade no lower than that computed by the following distribution of total points and weighted average conversion to letter grade:

Assignments = 40%
Midterm = 25% (given during week 8)
Final Exam = 35%

Weighted average conversion to letter grade
100-90%: A;  89-80%: B;  79-70%: C;  69-60%: D;  59-0%: F


Every assignment turned in must include a section labeled Reflection that includes your personal insights and observations. This section is expected and required, whether or not the assignment specification mentions it explicitly.

Formats of files turned in for assignments must not depend on specific operating systems or software that requires purchase or paid licensing. The following are examples of acceptable formats: ASCII text, UNICODE text, HTML, PDF, GIF, JPEG. The following are examples of unacceptable formats: Microsoft Word, AppleWorks. If the assignment consists of multiple files, you are encouraged to bundle them into an archive in tar, zip or sit format.

Late assignments will not earn course credit. You may submit an assignment after its due date for comments and advice, and you are encouraged to do so. However, the score for that assignment will be recorded officially as 0. Likewise, missing an exam will result in a score of 0 for that exam. Late homework and make-up exams will not be accommodated without prior arrangement and written agreement. Unforeseeable crises and emergency situations will be dealt with on a case-by-case basis in accordance with MSCD, College, and Departmental policies.

Note that significant information will be disseminated during class sessions or on the course website that you will be responsible for whether or not you attended the sessions or accessed the website. Not all information necessary to successfully complete the assignments or examinations is covered in the texts.


I encourage collaboration and regard it as essential aspect of Computer Science. Collaboration and discussion with fellow students concerning course information, materials, assignments, and studying for exams is encouraged. You are not expected to learn the course content or work on assignments in isolation on your own. However, you must write up your own solution, individually, to every problem you turn in even if the solution is the result of a collaborative effort. In your write-up, you must credit the people with whom you worked. If you consult any reference material other than the textbook, please note in your assignment which sources you used for each problem. Note that collaboration is not acceptable during any exam.

Course Outline:

Topic Reading
(Sipser text)
Background, Review, Introduction Chapter 0
Finite State Automata & Regular Languages Chapter 1
Pushdown Automata & Context-Free Languages Chapter 2
Turing Machines Chapter 3
Computability Chapter 4
Complexity (P, NP, NP-completeness) Chapter 7



Official Announcements:

Important Dates and Deadlines:

See MSCD Calendar

Class Attendance on Religious Holidays:

The college policy on Class Attendance on Religious Holidays is posted on the information board outside the Mathematical and Computer Sciences department office (SI141). In addition, copies of this policy are available from the department upon request. It is the students' responsibility to understand and abide by the policy.

American with Disabilities Accommodations:

Students desiring a reasonable accommodation under the ADA must contact the instructor immediately to discuss their needs. Failure to notify the instructor, in a timely manner, of the need for a reasonable accommodation may hinder the college's ability to assist students in successfully completing the course.

Labelled with ICRA

©2002,2003 Dr. Jody Paul