形式语言与自动机课程小结(北邮).

1、1College of Computer Science & Technology, BUPT 期末考试安排 时间时间 1月月5日（星期四）上午日（星期四）上午8:00至至10:00 地点地点 教教3-233 方式：方式： 开卷，开卷， 2College of Computer Science & Technology, BUPT 课程小结 自动机理论：自动机理论： 论述计算的数学模型、它们的定义和性质。论述计算的数学模型、它们的定义和性质。 n有限自动机、下推自动机、图灵机 形式语言层次：形式语言层次： n 正则（线性）语言、 上下文无关语言、 递归 可枚举语言与递归语言 3College

2、of Computer Science & Technology, BUPT 语言描述和处理机制语言描述和处理机制 有限自动机有限自动机 - 确定有限自动机确定有限自动机 DFA （DFA 的定义，语言，最小化，的定义，语言，最小化， 填表算法填表算法.） - 非确定有限自动机非确定有限自动机 NFA （ NFA 的定义，语言的定义，语言.） - NFA 的确定化的确定化（子集构造法（子集构造法. ） - 带带 -转移的非确定有限自动机转移的非确定有限自动机 -NFA （ -NFA 的定义，的定义， 语言，语言， -闭包，闭包， -NFA 消去消去 -转移）转移） 4College of Co

3、mputer Science & Technology, BUPT 语言的分类及其同语言描述与处理机制的关系语言的分类及其同语言描述与处理机制的关系 - 正则（正则（3型）语言型）语言 （正则表达式，正则文法，有限状态自动机（正则表达式，正则文法，有限状态自动机 ） - 上下文无关（上下文无关（2型）语言型）语言 （上下文无关文法，下推自动机（上下文无关文法，下推自动机.） - 递归可枚举（递归可枚举（0型）语言型）语言 （0型文法，图灵机型文法，图灵机. 若图灵机总能停机，则对应若图灵机总能停机，则对应递归递归 语言语言.） 5College of Computer Science & Te

4、chnology, BUPT - Pumping 性质性质 （针对正则语言和上下文无关语言的（针对正则语言和上下文无关语言的 Pumping 引理）引理） - 闭包性质闭包性质 （正则语言和上下文无关语言的交、并、（正则语言和上下文无关语言的交、并、 差、补、连接等运算的封闭性质，由封闭的运算构差、补、连接等运算的封闭性质，由封闭的运算构 造新的正则语言和上下文无关语言造新的正则语言和上下文无关语言.） - 判定性质判定性质 （判定各类语言是否空、非空、包含某个（判定各类语言是否空、非空、包含某个 字符串以及两个语言是否相等字符串以及两个语言是否相等. ） 语言的性质语言的性质 6Colleg

5、e of Computer Science & Technology, BUPT 语言描述和处理机制语言描述和处理机制-正则表达式正则表达式 正则表达式正则表达式 - 概念与性质概念与性质 （正则表达式的语法、语义，代数定律（正则表达式的语法、语义，代数定律.） - 与有限自动机的关系与有限自动机的关系（ 从从 DFA 构造等价的正则表达式构造等价的正则表达式-状状 态消去法；从正则表达式构造等价的态消去法；从正则表达式构造等价的 -NFA.） 7College of Computer Science & Technology, BUPT 语言描述和处理机制语言描述和处理机制-上下文无关文法上

6、下文无关文法 上下文无关文法上下文无关文法 - CFG 基础基础 （产生式，推导，归约，句型，（产生式，推导，归约，句型， 最左（右）推导，分析树，最左（右）推导，分析树， CFG 的语言的语言.） - 推导、归约与分析树之间的关系推导、归约与分析树之间的关系 - 文法二义性文法二义性 （相关的判定问题（相关的判定问题.） - 范式范式（消（消 -产生式，消单产生式，消无用符号，产生式，消单产生式，消无用符号， Chomsky 范式，范式，Greibach范式范式. ） 8College of Computer Science & Technology, BUPT 语言描述和处理机制语言描述和

7、处理机制- 下推自动机下推自动机 下推自动机下推自动机 - PDA 基础基础 （定义，格局，终态接受方式，空栈接受方（定义，格局，终态接受方式，空栈接受方 式，两种方式的等价性，式，两种方式的等价性，PDA 的语言的语言.） - PDA 与与 CFG 的关系的关系（从（从 CFG 构造等价的构造等价的 PDA，从从 PDA 构造等价的构造等价的 CFG.） 9College of Computer Science & Technology, BUPT 语言描述和处理机制语言描述和处理机制 - 图灵机图灵机 图灵机图灵机 - 基本图灵机基本图灵机 （定义，格局，（定义，格局，TM 的语言，构造技

8、术的语言，构造技术.） - 扩展的图灵机扩展的图灵机（多道，多带，双向无穷带机（多道，多带，双向无穷带机） 10College of Computer Science & Technology, BUPT 期末考试要求 1形式语言及文法形式语言及文法 n要求：掌握语言和文法的形式定义，CHOMSKY文法体 系的分类。 2有限自动机和右线性文法有限自动机和右线性文法 (FA和和3型文法型文法) n要求： n掌握DFA，NFA，有的NFA，米兰机，摩尔机的形式定 义 n右线性文法和有限自动机的等价性，要求会应用，看懂 证明 n右线性文法的性质，要求会使用泵浦定理证明。 11College of Computer Science & Technology, BUPT 期末考试要求 3下推自动机和上下文无关语言下推自动机和上下文无关语言(PDA和和2型文法型文法) n要求： n将上下文无关文法转换为CHOMSKY范式或 GREIBACH范式的文法表示(会变换，看懂证 明，掌握证明的思路) nPDA，DPDA的形式定义。 n2型文法和下推自动机的等价性，要求会应用， 看懂证明