CS403: Introduction to Formal Languages & Automata Theory
Course Catalog Description
Introduction to concepts and formalisms of formal languages and automata theory. Includes fundamental mathematical concepts, grammars and corresponding automata, and deterministic parsing of programming languages.
Overview
This course surveys the early days of computer science. We will start with a simple but useful model for computation and incrementally add capability. At each step, we will study the model’s power and limitations. Eventually the material formalizes the concept of an algorithm using a surprisingly simple abstraction known as a Turing machine.
This is a theoretical “pencil-and-paper” class. These days we have the benefit of stored-program general-purpose computers to check our reasoning – sometimes.
Understanding the foundational concepts and especially the limitations of various models will prepare you to competently analyze software problems, use certain features of your favorite programming language, and deploy test and cybersecurity strategies.
Objectives
Upon completion of this course, the student will be able to use and reason about:
- Deterministic and non-deterministic finite automata (DFAs and NFAs)
- Regular languages, regular expressions, and the pumping lemma for regular languages
- Limitations of DFAs and NFAs
- Context-sensitive grammars and pushdown automata
- Turing machines and the Church-Turing thesis
- The halting problem and decidability
Course Materials
- Required
- Optional/Recommended