Theory of Finite Automata
Book · Prentice-Hall
About the book
A textbook on finite automata and the languages they define. After a review of the discrete mathematics it relies on, it introduces the finite automaton and characterizes the languages that finite automata accept (Nerode's theorem and the pumping lemmas), then treats minimization, nondeterminism, closure properties, regular expressions, and finite-state transducers and their implementation as circuits. The closing chapters introduce formal languages more broadly: regular and context-free grammars, pushdown automata, Turing machines, and decidability.