西安交通大学研究生课程简介
课程编码： 052025
课程名称：（中）形式语言与自动机理论
课程名称：（英）·The Theory of Formal Language and Automata
学分数：3
课内总学时数：60
上机（实验）学时数：无
课程内容简介：
“形式语言与自动机理论”是一门专业理论基础课程。目的就是要加强学生的计算理论基础知识，培养专业技术理论的抽象能力。本课程主要介绍Chomsky定义的短语结构文法、前后文有关文法、前后文无关文法和正规文法，并证明了与这四类文法等价的四类自动机：图灵机、线性界限自动机、下推自动机和有穷自动机。最后，还讨论了非确定性、计算复杂性和NP完全问题等。
课外自学内容:
参照本课程相关内容，学生在课外学习计算理论基础和计算复杂性等方面知识，以加强对课内有关概念、定义、引理和定理的理解；深入掌握算法思想，提高理论研究工作的形式化描述和分析能力。
先修课: 离散数学
参考书目：
1、Harry R. L., Christos H. P.著，张立昂、刘田译。计算理论基础（第二版），清华大学出版社，2000
2、[美]A.V.阿霍，J.D.厄儿曼著；石青云译，形式语言及其句法分析，科学出版社出版， 1987
3、[美]J.E.霍普克罗夫特，J.D.厄儿曼著；莫绍揆，段祥，顾秀芳译，形式语言及其与自动机的关系，科学出版社出版，1979
执笔人：赵仲孟 审定人：冯祖仁
