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