形式语言与自动机总结.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 2PDA的语言 必须掌握 以终态方式接受以空栈方式接受从空栈方式到终态方式 包装 从终态方式到空栈方式构造PDA技术 6 3PDA与CFG的等价性 从文法到PDA 必须掌握 从PDA到CFG 不要求 6 4确定型的PDA 定义正则语言与DPDADPDA与CFLDPDA与歧义文法DPDA接受非歧义文法 但并不是所有非歧义文法都可由DPDA接受 S 0S0 1S1 e定理6 20 6 21空栈机 终态机与非歧义文法前缀性质与DPDA 第7章上下文无关语言的性质 本章是重点 7 1上下文无关文法的范式 文法的化简消除无用符号和产生式消除空产生式消除单产生式Chomsky范式 要求会转换 Greibach范式 7 2上下文无关语言的泵引理 的描述 的应用 重点 Ogden引理 P195习题7 2 3应用 7 3CFL的封闭性 代入 替换 封闭 并 连接 闭包 同态 逆同态不封闭 交 补CFL R是CFL 7 4CFL的判定性质 CFL与PDA转换的复杂度 略 CFG变换到CNF复杂度 不要求 测试空性测试成员性 CYK算法P209必须掌握 不可判定问题一览 参阅P211 第8章图灵机导引 重点 8 2图灵机 的定义ID q 的图形表示 的设计技术 必须掌握 的语言 作为函数 程序 停机问题 8 3图灵机的设计技术 状态中增加存储功能多道子程序技术 8 4图灵机的基本扩展 多带 非确定的 8 5受限制的 了解 半无穷带多堆栈机计数器机3计数器机可枚举语言 2计数器亦可 8 6TM与计算机 可用五带 模拟计算机 略 第9章不可判定性 了解重要结论 9 1非RE 图灵机的编码 必须会 枚举二进制串 正则排序Ld 对角化语言Ld非RE的证明通用图灵机的基本工作原理 9 2是RE但不可判定 递归语言及其补非递归的RE的补非RE通用语言LuLu的不可判定性 9 3与图灵机有关的不可判定问题 归约接受空语言的 Le与LneLne是RE但非递归Le是非RE的Rice定理与 有关的问题 参阅P271 9 4Post对应问题 略 第10章难解问题 了解 10 1P类