*Introduction to Automata Theory, Languages and Computation
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.
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
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.
• 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.
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
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.