一：图形总结。
重点：乔姆斯基体系
四大语法之间的关系：
总结全图：点击图片查看大图
(二)文字细节。
1、集合关系(并、交、补、差、笛卡儿积、幂积、二元关系) ) ) ) ) ) ) ) ) )。
1 )笛卡儿乘积(AXB，即，分别对应的乘积)。
例1-1，a={ 1，2，3 }，B={白，黑}
(AXB ) )、白)、(1，黑)、(2，白)、(2，黑)、(3，白)、(3，黑) }
2 )幂：2^A，即所有子集。
例1-2，a={ 1，2，3 }，
那么，2^A={ ，{1}，{2}，{3}，{ 1，2 }，{ 1，3 }，{ 2，3 }，{ 1，2，3 }
3 )二元关系：任意RAB，r为a到b的二元关系
2、句(前缀) )。
例2-1，文件abaabb
前缀：、a、ab、aba、abaa、abaab、ababb
真前缀：、a、ab、aba、abaa、abaab
后缀：、b、bb、abb、aabb、baabb、abaabb
后缀：、b、bb、abb、aabb、baabb
3、语法结构。
例3-1，L(G ) ) { a^n b^n|n，m0 )
s-ASB|ab (如果n，m=0，则为S-aSb|) )。
例3-2，L(g ) : ) a^nb^na^mb^m|n，m=0)
S-AB A-aAb| B-aBb|
4，)1)有确定的贫困状态机器人DFA。
特征：1)、初始状态是唯一的，最终状态可以有多个。
2 )、任意态任意射弧上的元素不相等
3 )、识别对象为空时，初始状态为终端状态。
结构：例4-1，L={x000y|x，y{ 0，1 } * }
最小化：
扫描所有状态对，找出所有可区分的状态对，不可区分的状态对一定是等价的。
)2)有不确定的贫困状态机器人NFA。
特征：1)、初始状态不唯一。
2 )、同一状态射出弧上的标记可以相同
3 )、初始状态可以是最终状态。
)3)-NFA
基于NFA，允许从当前状态直接转变到新状态，而不管输入向量上的符号如何
)4)等价性
1 ) NFA等效于DFA，且-NFA等效于NFA (NFA等效于DFA，且-NFA等效于NFA (统称为FA ) )。
2 )是FA与正规语法等价(FA与左线性语法，右线性语法等价) ) )。
对于一个输入字符，NFA和DFA的区别在于前者可以进入几种状态，后者只能进入一种唯一的状态。 从DFA的观点来看，NFA在某一时刻同时进入若干个状态，但是这些状态加在一起的“总效应”相当于与这些状态相对应的一个“综合状态”
5、正则表达式RE-----FA的转换规则
(1) ) ) )。
(2) ) ) )。
(3) ) )。
6、正则语言RL
)1)封闭性
1 )正则语言的并行、交叉、互补是正则语言。
2 )正则语言的乘积(连接)为正则语言。
3 )正则语言之差为正则语言。
4 )正则语言闭包为正则语言。
5 )正则语言商为正则语言。
6 )正则语言的同态是正则语言。
7 )正则语言逆转是正则语言。
附件：上下文相关语言CFL的封闭性
1 )并、积、闭包封闭
2 )不封闭传递、弥补
)2)泵引理
DFA在处理足够长的语句的过程中，必然会反复通过某个状态。 换句话说，在DFA的状态转换图中，必须存在从包含循环的起始状态到一个终止状态的路径。 因为是电路，DFA根据实际需要可以沿着该电路循环运行，由相当于电路中的弧线组成的非空部分矩阵可以任意重复。
)3)等效模型
7 .上下文相关语言CFL
)1)语法树
1 )每个句型至少存在一个语法树，每个语法树至少存在一个推导。
2 )每一片树叶组成句型(句型是我们的结果)。
3 )为每个简单子树的叶子建立一个简单的短语。
4 )最左边的简单子树的叶子构成句柄。
)2)简化CFG
1 )消除无用符号。
首先删除不能结束的东西，然后删除不能到达的东西
2 )脱空发生式
先求出空变量，再看空生成式对哪个生成式有影响
3 )去单一发生仪式
可能会生成新的无用符号或单一生成式
8、图灵机和计算机
)1)用计算机模拟图灵机。 不是所有的图灵机都可以由计算机模拟
模拟步骤：1)在计算机上打开大的一维排列来模拟输入带
2 )、将输入磁带存入数组
3 )、转换函数以什么样的数据结构保存
4 )编写穷举的计算机程序，在输入带上安装模拟图灵机运行
)2)图灵机的速度比计算机慢
)3)运行时间