CS603: Formal Languages & Automata Theory
Course Catalog Description
Formal definition of programming languages. Formal grammars: regular, context-free, context sensitive, and phrase-structure. Automata: finite-state, pushdown, linear-bounded automata, Turing Machines. Relationship between formal languages and automata.
Overview
This course examines seemingly simple concepts that we take as given when translating algorithms into source code that stored-program digital computers interpret or compile and ultimately execute. By the end of the course, we will appreciate these luxuries.
The course material and homework are largely pencil-and-paper exercises in reasoning, understanding proofs, and creating proofs of your own. Starting from an extremely simple model for computation, we will add small increments of capability. At each step, we will study the power and limitations of each.
Although the course’s focus is theoretical, we will discuss practical applications to design, implementation, test, and cybersecurity. Not only will the infamous answer on Stack Overflow about using regex to parse HTML make sense, you will understand why the approach is flawed and know better, more appropriate tools.
Objectives
Upon successful completion of this course, the student will understand:
- Formal grammars: regular, context-free, context-sensitive, and phrase-structure
- Automata: finite-state, pushdown, linear-bounded, and Turing machines
- Relationships between and among automata and classes of formal languages
- Decidability
Course Materials
- Required
- Optional/Recommended