Programming-Based Formal Languages and Automata Theory: Design, Implement, Validate, and Prove

This textbook introduces formal languages and automata theory for upper—level undergraduate or beginning graduate students. While it contains the traditional mathematical development usually employed in computational theory courses, it is also quite different from many of them. Machines, grammars, and algorithms developed as part of a constructive proof are intended to be rendered as programs.

The book is divided into four parts that build on each other. Part I reviews fundamental concepts...