前言

本书由“电子科技大学‘十二五’规划研究生教材建议基金”资助出版。

形式语言和自动机的理论是计算机科学的理论基础。这些理论来源于：

（1）Chomsky对自然语言的研究。

（2）Backus和Naur使用BNF（巴科斯－诺尔范式）对ALGOL-60语言的语法规则的描述方式。

（3）Turing、Kleene、Neumann、Huffman等对自动机模型的研究。

形式语言和自动机理论的应用范围已被扩展到生物工程、自动控制系统、图像处理与模式识别等许多领域。

形式语言与与自动机理论包括 3 方面的内容：形式语言理论、自动机理论和形式语言与自动机等价性理论。本书主要讨论自动机理论和形式语言与自动机等价性理论。

研究生的适应能力及创新能力在很大程度上取决于坚实的理论基础和专业基础知识，这是高质量研究生教育的重要特征之一。在当今计算机科学技术突飞猛进、专业知识日新月异的时代，只有扎实掌握专业的计算机理论基础，才有可能在该专业从事科研、教学和其他技术工作，才能打好进行创造性研究的基础。因此理论课程的学习就显得尤为重要。研究生理论课程教学，必须立足于提高研究生的学术水平和科研能力，是实现研究生培养目标、保证研究生质量的重要环节。

全书共分为7章。第1章回顾本书所需的基本数学知识；第2章是形式语言的基本内容，包括文法的定义、分类，文法的构造方法，以及语言之间的运算的封闭性的讨论；第3章、第4章介绍有限状态自动机的构造方法及其对应的正则语言的性质；第5章介绍下推自动机；第6章是对图灵机的讨论；第7章介绍量子图灵机。

本书的目标是，力求使计算机科学与技术学科各个专业的研究生掌握各类有限自动机的模型、构造方法和技巧，培养计算思维能力。

本书基本覆盖了形式语言的基本内容和有限自动机的主要内容，可以作为计算机科学与技术学科各专业研究生的教材。

本书不注重定理的烦琐证明过程，而强调问题的思考方法和思路的研究，以提高读者的创新思维能力。

本书是在第 1 版的基础上进行修订的，增加了有限自动机的应用、量子图灵机等内容。全书由陈文宇、田玲、程伟和刘贵松编著，龚天富教授审阅了全书。

感谢参考文献的作者和翻译人员。感谢电子工业出版社的王羽佳编辑为本书的出版所做的大量工作。本书在编写过程中，还得到了李维顺、郭凌立、朱建、袁野、曾红和陈青然等人的热情帮助，在此对他们及所有为本书的出版付出了辛勤劳动的同志表示衷心的感谢。

特别感谢北京工业大学的蒋宗礼教授，本书中借鉴了蒋宗礼教授的《形式语言与自动机理论（第2版）》的许多内容，且习题也来源于该书。

本书提供配套的课件，需要的读者请登录华信教育资源网（http://www.hxedu.com.cn）注册后免费下载。

由于编者水平有限，书中难免存在缺点和错误，殷切希望广大读者批评指正。

编著者