COMP 476: Formal Language and Automata
COMP 163 or Math 201 or Math 212
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.