形式语言与自动机课程考试复习纲要_机械设计课程复习纲要

形式语言与自动机课程考试复习纲要由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“机械设计课程复习纲要”。

形式语言与自动机课程考试复习纲要：

1.每个章节中的基本概念的理解和其相应的形式化定义

2.给定一个正则语言集合，构造相应的DFA,NFA，e-NFA或正则表达式的方法

3.DFA与NFA的等价性构造与数学归纳法的证明

4.正则表达式与有限自动机之间的相互转换方法

5.使用已有的自动机来构造新的自动机的形式化构造表示方法

6.应用正则语言Pumping 引理来证明一个语言是非正则语言

7.正则语言的等价判断与DFA的最小化方法

8.给定一个上下文无关语言，构造文法、PDA的方法，以及具体的一个字符串被PDA识别过程的形式化表达

9.上下文无关文法二义性的判断

10.CNF范式的转换方法

11.空栈接受方式的PDA与终止状态接受方式的PDA的等价性构造方法与证明

12.替换定理在上下文无关语言闭包性质证明中的应用 13判定一个字符串是否属于某个上下文语言的方法