形式语言与自动机总结.ppt

形式语言与自动机理论 西北工业大学计算机学院 康慕宁 2008.11 第1章 自动机：方法与体验 有限自动机常用类型 1．数字电路的设计和性能检查软件。 2．典型编译器的“词法分析器” 。 3．扫描大量文本(比如收集到的网页)来发现单词、短语或其他模式出现的软件。 4．所有类型的只有有穷多个不同状态的系统(比如通信协议或安全交换信息的协议)的验证软件。 第2章 有限（有穷）自动机 1．FA的形式化描述(五元组)、图表示、矩阵表示。 2．确定的~ ：DFA。 3．非确定的~ NFA及其确定化方法 4．带有空动作的NFA及其确定化 5. FA/DFA构造技术 第3章 正则表达式与正则语言 正则表达式的定义 FA与正则表达式的相互转换 从DFA到正则表达式的转换 ~代数定律 第4章 正则语言的性质 正则语言的泵引理及其应用（重点！） 第4章 正则语言的性质 ~的封闭性 交、并、补、差、闭包（*）、连接 反转 同态 逆同态 判定性质（各种表示之间的转换、空性、成员性） 最小化（状态的等价性、最小化的填表算法P106） 第5章 上下文无关文法及上下文无关语言 5.1 上下文无关文法 文法的定义及基本概念 推导、最左推导、最右推导 文法的语言 句型 文法的构造技术 5.2 语法分析树 构造~ 从推导到树 从树到推导 5.3 上下文无关文法的应用 程序设计语言 标记语言（例：HTML） 5.4 文法的歧义性 歧义文法 去除歧义性 固有歧义性 第6章 下推自动机 注意：本章是重点之一 6.1下推自动机的定义 非形式化介绍 形式化定义（七元组） PDA的图形表示 ID（瞬时描述、格局） (q,w,?) q表示状态 w表示余留输入串 ?表示堆栈中的内容 定理6.5 （P156） 6.2 PDA的语言（必须掌握） 以终态方式接受 以空栈方式接受 从空栈方式到终态方式（包装） 从终态方式到空栈方式 构造PDA技术 6.3 PDA与CFG的等价性 从文法到PDA（必须掌握） 从PDA到CFG（不要求） 6.4确定型的PDA ~定义 正则语言与DPDA DPDA与CFL DPDA与歧义文法 DPDA 接受非歧义文法，但并不是所有非歧义文法都可由DPDA接受。S-0S0|1S1|e 定理6.20,6.21空栈机、终态机与非歧义文法 前缀性质与DPDA 第7章 上下文无关语言的性质 本章是重点 7.1 上下文无关文法的范式 文法的化简 消除无用符号和产生式 消除空产生式 消除单产生式 Chomsky范式（要求会转换） Greibach范式 7.2 上下文无关语言的泵引理 ~的描述 ~的应用（重点） Ogden引理（P195 习题7.2.3 应用） 7.3 CFL的封闭性 代入（替换） 封闭：并、连接、闭包、同态、逆同态 不封闭：交、补 CFL∩R是CFL 7.4 CFL的判定性质 CFL与PDA转换的复杂度（略） CFG变换到CNF复杂度（不要求） 测试空性 测试成员性（CYK算法 P209 必须掌握） 不可判定问题一览（参阅P211） 第8章 图灵机导引 重点 8.2 图灵机 ~的定义 ID: ?q? ~的图形表示 ~的设计技术（必须掌握） ~的语言 ~作为函数（程序） 停机问题 8.3 图灵机的设计技术 状态中增加存储功能 多道 子程序技术 8.4 图灵机的基本扩展 多带~ 非确定的~ 8.5 受限制的~（了解） 半无穷带 多堆栈机 计数器机 3计数器机可枚举语言＝2计数器亦可 8.6 TM与计算机 可用五带~模拟计算机（略） 第9章 不可判定性 了解重要结论 9.1 非RE 图灵机的编码（必须会） 枚举二进制串，正则排序 Ld ：对角化语言 Ld非RE的证明 通用图灵机的基本工作原理 9.2 是RE但不可判定 递归语言及其补 非递归的RE的补非RE 通用语言 Lu Lu的不可判定性 9.3 与图灵机有关的不可判定问题 归约 接受空语言的~ Le与Lne Lne是RE但非递归 Le是非RE的 Rice定理 与~有关的问题（参阅P271） 9.4 Post对应问题 略 第10章 难解问题 了解 10.1 P类与NP类 多项式时间 非确定TM的多项式时间 NP例子：货郎担问题 多项式时间归约 NP完全问题 * * 对于给定的同态（或逆同态）映射，应能计算映射后的符号串及语言 *