本书阐述了计算科学的优美理论基础，通过演示计算理论在现代硬件和软件系统设计中的影响，把理论知识带到了现实实践之中。本书介绍了关键概念的应用，为读者在实际工作中使用计算理论提供实际指导。本书讨论的应用包括：程序设计语言、编译器、网络技术、自然语言处理、人工智能、计算生物学、安全性、博弈、商业规则建模、标识语言、Web搜索等。本书既适合作为自动机理论课程的教程，也是相关专业人员的重要参考用书。

Preface

Acknowledgments

Credits

PART Ⅰ INTRODUCTION

1 Why study the Theory of Computation?

2 Languages and Strings

3 The Big Picture: A Language Hierarchy

4 Computation

PART Ⅱ FINITE STATE MACHINES AND REGULAR LANGUAGES

5 Finite State Machines

6 Regular Expressions

7 Regular Grammars

8 Regular and Nonregular Languages

9 Algorithms and Decision Procedures for Regualr Languages

10 Summary and Reference

PART Ⅲ CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA

11 Context-Free Grammars

12 Rushdown Automata

13 Context-Free and Noncontext-Free Languages

14 Algorithms and Decision procedures for Context-Free Languages

15 Context-Free Parsing

16 Summary and references

PART Ⅳ TURING MACHINES AND UNDECIDABILITY

17 Turing Machines

18 The Church-Turing Thesis

19 The Church-Turing Thesis

20 Decidable and Semidecidable Languages

21 Decidability and Undecidability Proofs

……

PART Ⅴ COMPLEXITY

APPENDICES

APPENDICES G-Q: APPLICATIONS