The theory of computation is often viewed as one of the most abstract areas of computer science, mostly reserved for university courses. Yet its ideas power much of modern software: from regular expressions and compilers to animation systems and game AI. This book aims to bridge the gap between the formal world of the theory of computation and the realities of everyday programming practice.
Written in a clear, approachable style, it introduces the essential concepts of automata, formal languages, and computability. Through examples and practical connections, readers will see how theoretical models translate into the tools and systems developers work with every day. The book is designed for both students, taking basic computer science courses, and practicing developers who want to understand the theory behind the technologies they use but are not ready to dive
into a fully formal academic text.
Covering material aligned with the ACM/IEEE Computer Science Curricula, this book can serve both as a gentle textbook and a self-contained crash course for curious professionals. Striking a balance between rigor and intuition, it presents the theory of computation as a practical foundation of how software and computation really work.
Maxim Mozgovoy is a senior associate professor at the University of Aizu, Japan. He earned his PhD in Applied Mathematics from St. Petersburg State University and his PhD in Computer Science from the University of Joensuu. His main research interests are focused on educational technologies, natural language processing, and artificial intelligence for games and interactive environments. Maxim has a record of over 100 published papers and industrial-level software development experience. He is a co-founder of Helium9 Games studio, a regular reviewer for IEEE Transactions on Games and Entertainment Computing, and a program committee member of the IEEE Conference on Games, FedCSIS, Foundations of Digital Games, and other international conferences.
Table of Contents:
Chapter 1 Regular languages and regular expressions
Chapter 2 Finite automata
Chapter 3 Bridging regular expressions and finite automata
Chapter 4 State machines in software engineering
Chapter 5 Nonregular languages and context-free grammars
Chapter 6 Pushdown automata
Chapter 7 Parsing
Chapter 8 Building compilers
Chapter 9 The Lindenmayer systems
Chapter 10 Turing machines
Chapter 11 Decidability and complexity
About the Author :
Maxim Mozgovoy is a senior associate professor at the University of Aizu, Japan. He earned his PhD in Applied Mathematics from St. Petersburg State University and his PhD in Computer Science from the University of Joensuu. His main research interests are focused on educational technologies, natural language processing, and artificial intelligence for games and interactive environments. Maxim has a record of over 100 published papers and industrial-level software development experience. He is a co-founder of Helium9 Games studio, a regular reviewer for IEEE Transactions on Games and Entertainment Computing, and a program committee member of the IEEE Conference on Games, FedCSIS, Foundations of Digital Games, and other international conferences.
