Skip to Main Content

MASTER SYLLABUS

Master Syllabus

Print this Syllabus « Return to Previous Page

Administrative Unit: Computer and Mathematical Sciences Department
Course Prefix and Number: CISS 362
Course Title: *Introduction to Automata Theory, Languages and Computation
Number of:
Credit Hours 3
Lecture Hours 3
Lab Hours 0
Catalog Description:

The study of formal languages, grammars, abstract computer models, and computability. Different models of computation and their relationships with formal languages as well as capabilities and limitations of these models are studied from a theoretical perspective. Cross-listed as MATH 362.  Prerequisites: MATH 225 and CISS 240.

 
Prerequisite(s) / Corequisite(s):

MATH 225 and CISS 240.

 
Course Rotation for Day Program: Offered even Fall.
 
Text(s): Most current editions of the following:

Textbooks listed are not necessarily the textbook(s) used in the course.

Introduction to Automata Theory, Languages, and Computation
By Hopcroft, J. E., Motwani, R., Ullman, J. (Addison Wesley)
Recommended
Elements of the Theory of Computation
By Lewis, H. R., Papadimitriou, C. (Prentice-Hall)
Recommended
Introduction to the Theory of Computation
By Sipser, M . (Brooks Cole)
Recommended
Languages and Machines: An Introduction to the Theory of Computer Science
By Sudkamp, A. (Addison Wesley)
Recommended
 
Course Objectives

  • To develop a strong foundation for understanding computation and complexity through the study of abstract models of computation, languages, algorithms, and computational complexity.
  • To develop the mathematical foundation for the study of topics such as computer architecture, language design, compiler construction and mathematical logic.
  • To develop rigorous training in mathematical reasoning and to greatly improve personal mathematical sophistication and problem-solving skills.

  •  
    Measurable Learning Outcomes:

    • Construct an NFA/DFA given the desired behavior of the machine in words. • Translate between NFA/DFA, regular sets and regular expressions. • Prove if a given language is regular by stating a corresponding DFA, NFA or regular expression. • Prove a language is not regular using the Pumping Lemma for regular languages. • Construct the minimal DFA from an NFA. • Translate between PDA, CFG, and CFL. • Prove a language is not a CFL by using Pumping Lemma for CFL. • Construct an equivalent CFG in Chomsky/Greibach normal form when given a CFG. • Prove if a word is in a CFL using Cooke-Younger-Kasami algorithm. • Construct a Turing machine given the behavior of the machine in words. • Prove if a language is recursive or recursively enumerable. • Prove if a problem is decidable or undecidable. • Prove a given problem is NP-complete.

     
    Topical Outline:

  • Preliminaries: - Set theory - Mathematical induction - Languages
  • Finite automata and regular expressions: - Deterministic finite automata - Nondeterministic finite automata - Regular expressions and languages - Finite automata with output - Applications of finite automata - Pumping lemma for regular sets - Closure properties of regular sets - Decision algorithms for regular sets - Myhill-Nerode theorem
  • Context-free grammars, context-free languages and pushdown automata - Context-free grammars and context-free languages (CFLs) - Derivation trees - Simplification of context-free grammars - Chomsky normal form - Greibach normal form - Inherently ambiguous CFLs - Pushdown automata - Pumping lemma for CFLs - Closure properties of CFLs - Decision algorithms for CFLs - Cooke-Younger-Kasami algorithm - LL and LR grammars (optional)
  • Turing machines - Turing machine - Computable languages and functions - Techniques for Turing machine construction - Modifications of Turing machines - Church's hypothesis - Turing machines as enumerators - Restricted Turing machines equivalent to the basic model - Recursive function theory: primitive recursive and partial recursive functions
  • Undecidability - Recursive and recursively enumerable languages - Universal Turing machines and an undecidable roblem - Rice's theorem
  • Computational complexity theory - Linear speed-up, tape compression, reduction in number of tapes - Hierarchy theorems - Polynomial time and space - Nondeterministic polynomial time - P vs NP - Polynomial-time reductions - NP-complete problems - Cook's theorem

  •  
    Culminating Experience Statement:

    Material from this course may be tested on the Major Field Test (MFT) administered during the Culminating Experience course for the degree. 
    During this course the ETS Proficiency Profile may be administered.  This 40-minute standardized test measures learning in general education courses.  The results of the tests are used by faculty to improve the general education curriculum at the College.

     

    Recommended maximum class size for this course: 20

     
    Library Resources:

    Online databases are available at http://www.ccis.edu/offices/library/index.asp. You may access them from off-campus using your CougarTrack login and password when prompted.

     
    Prepared by: Yihsiang Liow Date: November 17, 2009
    NOTE: The intention of this master course syllabus is to provide an outline of the contents of this course, as specified by the faculty of Columbia College, regardless of who teaches the course, when it is taught, or where it is taught. Faculty members teaching this course for Columbia College are expected to facilitate learning pursuant to the course objectives and cover the subjects listed in the topical outline. However, instructors are also encouraged to cover additional topics of interest so long as those topics are relevant to the course's subject. The master syllabus is, therefore, prescriptive in nature but also allows for a diversity of individual approaches to course material.

    Office of Academic Affairs
    12/04