Theory of Computation

Automata, Formal Languages, Computation and Complexity

Author: K. R. Chowdhary

Publisher: Springer Singapore

Publication: 2025

eBook ISBN: 978-981-97-6234-7

Hardcover ISBN: 978-981-97-6233-0

Pages: 644

About the Book

Theory of Computation presents a comprehensive study of mathematical models of computation, formal languages, automata, computability, and computational complexity. The book is designed to develop a systematic understanding of how computational systems can be formally described, analyzed, and classified.

The book combines mathematical foundations with computational models and practical applications. Its pedagogical approach uses carefully developed explanations, examples, learning outcomes, chapter summaries, and exercises to help students understand both the theory and its significance in Computer Science.

Major Topics Covered

• Mathematical preliminaries for the Theory of Computation
• Finite automata and regular expressions
• Variants and minimization of finite automata
• Regular languages and their properties
• Context-free grammars and context-free languages
• Normal forms of context-free grammars
• Pushdown automata and parsing
• Turing machines and computability
• Extensions of the basic Turing machine
• Linear-bounded automata and context-sensitive languages
• Chomsky hierarchy
• Decidability, undecidability, and unsolvability
• Computational complexity theory

Connecting Theory with Computer Science

An important feature of the book is its attention to relationships among different computational models and to applications that connect theoretical concepts with practical computing. The treatment includes applications of finite automata and regular languages, relationships between formal-language models, and topics closely related to compiler theory.

The book also emphasizes the boundaries of computation by examining decidability, undecidability, unsolvability, and computational complexity. These topics provide an essential foundation for understanding what computers can compute, what cannot be computed algorithmically, and the resources required to solve computational problems.

For Undergraduate and Postgraduate Study

Selected chapters are suitable for undergraduate courses in B.Tech. and B.E. Computer Science. The later material can also support Master's-level study in advanced Theory of Computer Science, including courses in M.E. and M.Tech. programmes.

The book can additionally serve as a foundation for students and researchers who wish to pursue further study in automata theory, formal languages, computability, complexity theory, compiler theory, and related areas of theoretical Computer Science.

Key Features

• Pedagogical presentation suitable for university-level study
• Extensive exercises and carefully structured learning material
• Coverage of classical and extended computational models
• Applications connecting theory with practical computing
• Treatment of the extended Chomsky hierarchy
• Discussion of decidability, undecidability, and unsolvability
• Introduction to computational complexity
• Material suitable for both undergraduate and advanced postgraduate study