This classic book on formal languages, automata theory and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with increased coverage of practical applications. This new edition offers students a more informal writing style while providing the most accessible coverage of automata theory, solid treatment on constructing proofs, many figures and diagrams to help convey ideas and sidebars to highlight related material. Each chapter offers an abundance of exercises for hands-on learning.