形式语言与自动机 （Formal Languages and Automata） --- 前 言 南京航空航天大学 计算机科学与技术学院 关东海 副教授 dhguan@nuaa.edu.cn 简单解释一下有关 形式语言（formal language ）和自动机的含义。
本课程的主要内容和地位 形式语言– 研究字符串集合及其性质的学科 语言包括自然语言和人工语言 字符串是计算机处理的主要对象 自然语言是人和人之间交流的基本手段，如汉语、英语、法语等 人工语言主要用于人和计算机之间的交流，如程序设计语言 2
本课程的主要内容和地位 形式语言 自动机 研究自然语言和人工语言都必须遵循的一般规律 语言（形式语言）识别器 可见，本课程是计算机科学的基本理论！ 3
为什么要学习计算机的理论课程？ 几个问题： 理论（theory）的作用： 现在的计算机看上去无所不能，有没有它不能做的事情？（可计算性与不可计算性，难解性） 各种计算机（巨型机、台式机、笔记本、手机等）外形各异，计算能力本质上相同吗？（图灵机） 编程语言很多，为什么都一定要有编译器?为什么没有中文的编程语言与编译器？（形式语言理论） 理论（theory）的作用： 任何一个学科都有其基础理论模型； （牛顿三大运动定律；元素周期律）; 形式语言与自动机理论：计算机科学的基础理论
本课程的学习与考核要求 课堂学习： 课后作业： 学习主要的原理、方法以及思路； 积极参与交流 考核: 仔细阅读教材及参考资料的相关部分； 习题 使用工具：JFLAP: http://www.jflap.org/ 中文网址： http://hujun.nuaa.edu.cn/Courses/jflap-tutorial/JFLAP.html 考核: 期末考试：65% 平时成绩：35%
课程内容 1. 预备知识 2. 文法一般理论 3. 有穷自动机 4. 正则表达式 5. 正则语言的性质 6. 上下文无关文法 7. 下推自动机 8. 上下文无关语言的性质 9. 图灵机导引 10. 不可判定性 11. 上下文相关文法(*) 12. 确定的上下文无关语言与LR(k)文法(*)
教材及参考书 教材：《形式语言与自动机》，陈有祺 著 参考书： 《自动机理论、语言 与计算导论》 《形式语言与自动机理论》 《形式语言与自动机导论》 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman 蒋宗礼 林茨 7 7