COMP 376: Formal Languages and Automata

Course Information


This course introduces formal language theory, including such topics as finite automata and regular expressions, pushdown automata and context-free grammars, Turing machines, undecidability, and the halting problem.


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 the 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 a compiler design, computability theory, Church-Turing thesis, Turing machines, undecidability, recursive and recursively enumerable languages, reductions among languages, resource-bounded computation, Kolmogorov complexity.


An understanding of the theoretical underpinnings of computability and complexity in computer science.


See the Current Course Syllabi.