An Introduction to Finite Automata and their Connection to Logic
Howard Straubing, Pascal Weil · Co-Published with Indian Institute of Science (IISc), Bangalore, India eBooks · 2012
This is a tutorial on finite automata. We present the standard material on determinization and minimization, as well as an account of the equivalence of finite automata and monadic second-order logic. We conclude with an introduction to the syntactic monoid, and as an application give a proof of the equivalence of first-order definability and aperiodicity.