Jody Paul (Logo) Dr. Jody Paul – EducationMSCD Courses
Theory of Computation
jody@acm.org    
     
Link to Home Page for Jody Paul Link to the Education section main page Link to Software Engineering section Link to Music section Link to Recommendations section
    Link to MSCD Courses page        

Course Information

Title: Introduction to the Theory of Computation
Institution: Metropolitan State College of Denver
Semester: Spring 2008 (January 22 - March 15)
ID [CRN]: CS 3240 [33474]
Meeting Times:

Tuesdays & Thursdays, 1:00 PM - 2:50 PM

Location:

Science 113

Prerequisites: CS 3050 and MTH 3100
Course Website: http://www.jodypaul.com/cs/theory
Course Support: http://www.jodypaul.com/moodle/
Instructor: Dr. Jody Paul (schedule & office hours)
E-mail: jody@cse.mscd.edu
Office: Science 225C
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

Resources:

Textbooks:
Image of Book Cover - Introduction to the Theory of Computation / Link to Amazon.com

Introduction to the Theory of Computation
 [Amazon]
by Michael Sipser
Course Technology; 2nd edition (2005)
ISBN 0-534-95097-3
Textbook Errata

jflap text / link to Amazon.com

JFLAP: An Interactive Formal Languages and Automata Package
 [Amazon]
by Susan H. Rodger & Thomas W. Finley
Jones and Bartlett (2006)
ISBN 0-763-73834-4

Application:
 

JFLAP
A package of graphical tools that aid in learning the basic concepts of Formal Languages and Automata Theory

JFLAP Website


Computation & Connectivity:
Participants need to use JFLAP and to access the World Wide Web and MSCD e-mail accounts. Note that all participants receive access to necessary technology resources by virtue of being students at MSCD (see: http://www.mscd.edu).

Policies:

Significant information will be disseminated during class sessions or on the course website that you are responsible for whether or not you attended the sessions or accessed the website. That is, all information necessary to successfully complete the course is not necessarily covered in the texts.

Assignments & Practice

Note that extensive hands-on practice is necessary to achieve the required level of understanding and technical ability. Experience has shown that such practice is also necessary for successful performance on the exams.

Exercises are assigned that specifically target these objectives. You are strongly advised to work through all assigned exercises, by hand, and to attempt as many additional exercises as you need to develop facility with the concepts and techniques.

You are expected to use JFLAP to verify your solutions, as well as to experiment and explore the course material.

Assignments represent your opportunity to learn the material and you are not responsible for mastery of the material until the midterm and final exams. Thus, assignment solutions themselves are not graded. Instead, a write-up is required for each assignment set, in which you are expected to reflect on the experience of working on the assignment and report personal insights and observations.

Collaboration

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. Assigned exercise solutions are not graded in part to encourage collaborative learning and study. You are not expected to learn the course content or work on assignments in isolation on your own. Note that collaboration is not acceptable during any exam.

Grading

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

Distribution:
Assignment write-ups = 10%
Midterm = 35% (given during week 4)
Final Exam = 55% (given during week 8)

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

 

Official Announcements:

Official policies applicable to all courses: http://cs.mscd.edu/metadot/index.pl?iid=2249

Also see the MSCD College Catalog at http://www.mscd.edu/academic/catalog/ for official announcements, including Academic Policies and Procedures and Student Rights and Responsibilities, and the Academic Calendar at http://www.mscd.edu/academic/acal.htm for additional official dates and deadlines, including the last dates to withdraw and receive NC (with and without faculty signatures).

Valid HTML 4.01 Transitional ©2002,2003,2006,2008 Dr. Jody Paul – All Rights Reserved