An Introduction to Theory of Computation

This textbook aims to provide a comprehensive introduction to the theory of computation for upper-level undergraduate students and first-year graduate students in computer science and related disciplines. It covers a wide range of foundational topics essential for understanding the principles and applications of computation.

The book begins with regular languages, exploring finite automata, nondeterministic finite automata, regular expressions, and the equivalence among these apparatuses. It explores state minimization and the Myhill-Nerode Theorem, offering techniques such as pumping lemmas to identify non-regular languages and using the Myhill-Nerode Theorem for non-regularity proofs. Additionally, the closure properties of regular languages are examined.

Context-free languages are another focal point, where the text discusses context-free grammars, Chomsky normal form grammars, pushdown automata, and their equivalences. The book includes pumping lemmas and closure properties using CNF grammars and PDA analysis, as well as identifying non-context-free languages and understanding leftmost derivations.

Turing machine models are thoroughly covered, with various models and simulations explained. The book outlines configurations, the Church-Turing Thesis, and differentiates between recursive and recursively enumerable languages.

Decidability and undecidability are critical topics in the text, addressing decidable problems, diagonalization, the halting problem, and Rice’s Theorem. It also provides a characterization of decidability, discusses the Post Correspondence Problem, and examines the lower levels of the arithmetical hierarchy.

The textbook also delves into computational complexity classes, defining time and space complexity classes, and presenting efficient simulations and hierarchy theorems, including the Hennie-Stearns Theorem. It includes examples of problems in P and NP, providing a clear understanding of these classifications.

NP-completeness is explored in detail, covering SAT and 3SAT, canonical complete problems, and various NP-complete problems. The book extends to space complexity classes, discussing PSPACE complete problems, NL-complete problems, and proving that NL=coNL.

Finally, the text ventures beyond NP-completeness, discussing Ladner’s construction of non-NPC sets, randomized complexity classes, and concepts such as BPP and the polynomial hierarchy. It also examines polynomial size circuits, providing a comprehensive view of the landscape of computational complexity.

Dr. Mitsunori Ogihara joined the University of Miami in 2007 as a Professor in the Department of Computer Science and as the Director of Big Data Analytics & Data Mining in the Center for Computational Science. He serves as the Director of Education and Workforce Development in the Frost Institute for Data Science (he is currently the Director of Master of Science in Data Science and Site co-Director for NSF IUCRC CARTA).

Dr. Ogihara obtained his PhD in Information Sciences from the Tokyo Institute of Technology in 1993. From 1994 to 2007, Dr. Ogihara was a Computer Science faculty member at the University of Rochester, where he was promoted to Associate Professor with tenure in 1998, and to Full Professor in 2002. He also served as Chair of the Department from 1999 to 2007.

His research interests include data mining, information retrieval, network traffic data analysis, program behavior analysis, molecular computation, and music information retrieval. A prolific scholar, Dr. Ogihara has authored/co-authored four books The Complexity Theory Companion, Music Data Mining, Exploring Data Science with R and the Tidyverse, and for Springer, Fundamentals of Java Programming, and is the author of more than 200 peer-reviewed research papers. Many papers by Dr. Ogihara are through interdisciplinary collaborations. His articles appear in journals and conferences that cover many fields, including psychology, implementation science, library science, chemistry, biology, and digital humanities. He serves as Editor-in-Chief for the Theory of Computing Systems Journal (Springer) and on the editorial board for the International Journal of Foundations of Computer Science (World Scientific).