COMP 476: Formal Languages and Automata

Credit Hours



COMP 163: Discrete Structures or MATH 201: Elementary Number Theory or MATH 212: Linear Algebra

All MS students are expected to have completed the undergraduate prerequisites:

Please note that MS IT students are expected to complete all prerequisites before taking any course in CS or the Quinlan School of Business. (This includes any additional prerequisites required by Quinlan.)


This course will study three mutually related topics: languages, machines, and computability. The mathematical ideas developed in this course are useful in many areas of computer science, including the design and specification of programming languages, construction of compilers, and exploring the capabilities and limitations of mechanical computation. This subject is important for the scientific foundations it lays for computer science, for the philosophical concerns it raises about the nature of computation, and for the sheer elegance it brings in to the studies related to a variety of applications. Some of the most fundamental discoveries in computer science identify connections among languages, machines, and computability. Furthermore, some of the most challenging questions at the heart of computer science also arise from these topics. The course will cover a majority of the following topics: regular languages, finite automata, determinism and nondeterminism in finite automata, applications to searching and pattern matching, context-free languages, push-down automata, applications to compiler design, computability theory, Church-Turing thesis, Turing machines, undecidability, recursive and recursively enumerable languages, reductions among languages, resource-bounded computation, Kolmogorov complexity.


No recent syllabi available.