Automata Theory with Modern Applications

Recent applications to biomolecular science and DNA computing have created a new audience for automata theory and formal languages. This is the only introductory book to cover such applications. It begins with a clear and readily understood exposition of the basic principles, that assumes only a background in discrete mathematics. The first five chapters give a gentle but rigorous coverage of regular languages and Kleene’s Theorem, minimal automata and syntactic monoids, Turing machines and decidability, and explain the relationship between context-free languages and pushdown automata. They include topics not found in other texts at this level, including codes, retracts, and semiretracts.