The theory of computing provides students with a background in the fundamentals of computing with which to achieve a deeper understanding of contemporary computing systems. Computers are evolving and developing at a dizzying rate. Yet, the fundamentals of pattern matching and programming language design and implementation have remained unchanged. In this book, we present a perspective on computing that will always apply since it addresses only the fundamental issues. In this way, mastery of the topics in this book will give the reader a perspective from which to understand all computers, not just the ones in use today.

We cover the automata and regular languages that serve as the basis for patternmatching algorithms, communication protocols, control mechanisms, sequential circuit design, and a host of other ubiquitous applications. The basic principles behind the parsing of computer languages are also presented as well as a simple, yet general, model of all computation. This leads to some important distinctions. Some problems of interest turn out to be unsolvable. That is, not only can they not be solved by today's computers, but they will also never be solved by any future computer.Some problems that are solvable are nonetheless so difficult that they are called intractable. These intractable problems cannot be solved efficiently by any current computer. Furthermore, advances in the design of computers will not make a significant difference.

This book focuses on fundamental issues of computation. The readers can master the content and gain lasting perspective from which to understand computers by carefully worked out examples, illustrations, and algorithmic proofs. Teaches the fundamental concepts behind computation. Hundreds of exercises marked according to the level of difficulty provide readers ample opportunity to apply concepts. Hundreds of illustrations which enhance understanding. Only algorithmic proofs are given in the text allowing readers to calibrate the mathematical depth they want to pursue. Appropriate for upper division undergraduate and graduate level courses in Computer Science Theory, Theory of Computation, and Automata and Formal Language Theory.