Master Syllabus

 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 ComputationBy Hopcroft, J. E., Motwani, R., Ullman, J. (Addison Wesley) RecommendedElements of the Theory of ComputationBy Lewis, H. R., Papadimitriou, C. (Prentice-Hall) RecommendedIntroduction to the Theory of ComputationBy Sipser, M . (Brooks Cole) RecommendedLanguages and Machines: An Introduction to the Theory of Computer ScienceBy 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 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 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.