《形式语言理论复习2010(教师版)》由会员分享，可在线阅读，更多相关《形式语言理论复习2010(教师版)（5页珍藏版）》请在金锄头文库上搜索。
1、 形式语言理论复习提纲一、形式语言理论概述 1. 形式语言理论的两个核心问题是什么？(语言的描述与识别)2. 熟悉语言的如下运算：连接、幂、闭包、正闭包。3. 熟悉文法的定义与作用。4. 会根据给定的文法与语句进行推导。5. 文法的乔姆斯基谱系包括哪四种文法？分别生成什么语言？对应的识别器分别是什么自动机？二、正规表达式与正规文法1. 熟悉正规表达式的基本定义。2. 能够为指定的语言设计正规表达式。3. *解正规表达式方程组。4. *了解左线性文法与右线性文法的特点。5. *根据右线性文法求出等价的正规表达式。三、有限自动机1. DFA 的物理构成、形式定义、状态图、计算方式和接受条件。2.
2、NFA 的形式定义、计算方式和接受方式。 （1.一般的 NFA 与 DFA 在状态图上有什么的不同？2. 接受条件与 DFA 有什么不同？）3. 设计 DFA、NFA。4. 由 NFA 得到等价 DFA 的子集法。5. 由正规表达式构造等价的 NFA 的汤姆逊算法。6. *由 NFA 构造等价的右线性文法。7. 正规语言的泵引理：内容、证明和应用。8. 一个语言所确定的等价关系，一个 DFA 所确定的等价关系，与 Myhill-Nerode 定理。9. *设计一个从文本文件中找出其中第一个自然数的DFA。10了解 Moore 机与 Mealy 机的指令格式、含义与转移图。四、上下文法无关文法1
3、. CFG 与编程语言之间的关系。2. CFG 与巴克斯 -瑙鲁范式之间的关系。3. 哪一个编程语言的文法首先使用巴克斯-瑙鲁范式进行描述的？4. 语法分析的目的、方法。5. 推导树的定义、作用。6. 短语的含义。7. 最左推导与最右推导；最左归约。8. 最左推导与推导树的关系。 （一一对应吗？）9. 文法歧义性的含义。 （编程语言能否有歧义性？）10. *了解上下文无关文法的三种化简：消除无用字符、消除空产生式、消除单产生式。11. 熟悉乔姆斯基范式与格雷巴赫范式的特点。五、下推自动机1. 物理构成、基本定义、指令格式与含义、状态图、计算方式、空栈方式接受条件。2. 什么是 DPDA？与 P
4、DA 等价吗？3. 了解 PDA 与 CFG 之间的等价性。4. 上下文无关语言的泵引理：内容、证明和应用。5. *了解 Orgden 引理的内容。 （两相比较：Orgden 引理的优点、泵引理的优点）五、图灵机1. 图灵机的基本概念、指令格式与含义、状态图。2. 作为识别器的图灵机的计算方式与接受条件。3. 递归可枚举语言与递归语言的含义；两者之间的关系。4. 了解一点知识，与图灵机等价的计算模型有：lambda 演算系统、递归函数系统、命题逻辑证明系统、随机存取机(RAM)，等等。5. 丘奇-图灵论题的内容与意义。6. 了解图灵机编码、通用语言与通用图灵机的概念。7. 通用图灵机与计算机的
5、诺依曼体系的关系。8. 了解线性界限自动机的定义与所识别的语言。9. 什么是线性界限自动机问题？六、语言运算的封闭性1. 了解正规语言的封闭性。2. 了解上下文无关语言的封闭性。七、判定问题与可判定性1. 什么是判定问题？2. 什么是可判定的问题？3. 什么是停机问题？4. 如何论证停机问题是不可判定的？（了解其中的对角线构造法）5. 停机问题的意义：第一个不可判定问题；停机问题的不可判定性可以推出数学命题的真假是不可判定的。从而解决了希尔伯特 1928 年提出的关于数学基础的三个著名问题中的第三个问题。注：1930 年年仅 24 岁的数学家哥德尔解决了其中的第一个问题：任何包含算术公理的数学系统是不完备的；1931 年哥德尔解决了第二个问题：任何包含算术公理的数学系统的相容性是自身不能证明的。八、时间复杂度1.函数增长速度的渐进记号：大 O 记号，大 记号，大记号2.确定的图灵机的时间复杂度：时间复杂度上界与下界。3.非确定的图灵机的时间复杂度：时间复杂度上界与下界。4.问题的时间复杂度：时间复杂度上界与下界。5. NP 完全问题。6.第一个 NP 完全问题： SAT 问题。
