6.继续求出B和C所对应的Ia Ib ，再检验：对于DEFG这四个状态集合，有没有与ABC是不同的，如果有，加入到第一列的下面，再继续计算，如果与前面的ABC相同就不再需要加入了。
7.按照这样的方法一直进行下去，知道第一列不再有新的状态集合加入了，这个表就构造好了。
8.再画一张表，与上面的表相对应
S 0 1 2 3 4
a 1 3 4 2 …
b 2 4 3 1 …
9.对于上面这种表的构造方法很简单，大家也可以不另外画表，而直接标在原来的表中 这种表来源是，在原来表的第一列上分别表上s01234···，a和b不变，然后按照第一列中数字所对应的状态集，依次对应在后面的列上标上相应数字。例如第一列中B对应1，C对应2，那么将第二列第二行中的B也标上1，第三列第二行中的C标上2，等等。 10.画出下面的这个表或在原表中标好后，就可以按照这个表画出状态转换图了，例如，0状态通过a弧转换成1状态，通过b弧转换成2状态；1状态通过a弧转换成3状态，通过b弧转换成4状态，等等。画出这个状态转换图后，就完成了一个非确定有限自动机的确定化。
11.有限自动机DFA的化简
整体的思路如下：
1.将第10步中得到的已经确定的DFA中的所有状态分为两组，一组为终态节点，一组为非终态
节点。需要补充的是，在上一步构造的表格中，s那一列的节点哪些是终态哪些是非终态呢？这需要看你最初构造的正规式中的哪个是终态节点了。例如在下面的12中，Y为终态节点，那么在以上的表格中只要是含有Y元素的状态集合都将成为终态集。
2.将每个分组检验，看他们是否还能分割，检验的方法实在难以用文字描述清楚，请大家看下面的实际例题，自己领会。
3.每个分组都不能再分割后，若还含有大于2个元素的分组，则这个分组中的所有状态都是等价的，可以用其中的一个代替他们，代替的方法是：假设用状态1代替状态2，则把状态2及其引出去的弧全部删去，并把原来指向状态2的弧指向状态1
下面是老师复习PPT上的一个例子，这是一个较为复杂的例子，可能会看不懂，大家多问一问周围会的同学，期末考试时，肯定不会出这么复杂，通常在将终态节点和非终态节点区分开后，剩下的就已经快分好了，所以大家不用太担心，化简也是有可能不考察的，大家看清题目要求。 例：
12.
例题：构造一个DFA，它接受∑={x，y}上所有倒数第二个字符为y的字符串
说明一下这道题的解题思路和步骤，希望大家能真正明白整个解题的过程，让大家真正明白这样的一道大题是应该怎么做的.
上面这道题的分析思路是
1.根据他所描述的功能，构造出一个正规式，正规式先给大家：（x|y）y (x|y) （其实对于这样的大题最关键就是构造对正规式，大家一定把老师最后的PPT上所有的例题是如何构造正规式的都记下来！这一步做不出来后面的都没分了！） 2.构造一个初始状态X和和最终状态Y，将正规式写在他们的转换弧上。
*
3.按照第8点中的分裂规则对他进行分裂，分裂直到每一条转换弧上都只含有一个字符 4.分裂结束得到的一个状态转换图实际上就是一个NFA（非确定的有限自动机） 5.在掌握了第9点知识的前提下，就可以按照第10点说的步骤，将求得的NFA确定化 6.得到确定化之后的状态转换图，剩下的事情就是化简了。也就是第11点当中的只是
看到这里强烈建议大家先动笔试一试上面这道例题，相信只要你认真学习了前面的知识，做出来是没有问题的，祝大家成功！
三：语法分析 （1）基本定义
1.上下文无关文法的定义
文法：是描述语言的语法结构的形式规则（或称语法规则） 上下文无关文法概念:
它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的（与它所在的上下文无关）
（重要！以下的概念一定要理解熟知！）
上下文无关文法G可定义为一个四元式(VT，VN，S，P)
VT是终结符号集合，它的每个元素称为终结符号，用小写字母表示。 VN是非终结符号集合，它的每个元素称为非终结符号，用大写字母表示。 S是一个开始符号，是一个非终结符，至少在一个产生式作为左部出现
P是一个产生式的集合，它的每个元素称为一条产生式，可以表示为：P→α| b，其中P 是非终结符，叫做产生式的左部，α和b分别叫做这个产生式的一个侯选式，他们既可以是终结符，也可以是非终结符，也可以是他们的组合。
2.句型、句子的概念（小题）
设G是一个文法，S是它的开始符号，如果S
α，且α∈(VN∪VT) 则称α是G
*
的一个句型；如果S 有终结符号的句型
α，且α∈ VT ，则称α是G的一个句子；句子实际上是仅含
*
3.文法和语言的对应关系：（了解）
一个文法G所产生的句子的全体就是一个语言。给定一个文法，就能从结构上唯一确定其语言；给定一种语言，能找到其文法，但该文法不是唯一的
4.语法分析树与二义性：（了解）
用一棵树来表示句型的推导，简称语法树。若一个文法的一个句子对应两棵不同的语法树，则称该句子是二义性句子如果一个文法含有二义性的句子，则称该文法是二义性文法。
（5,6,7均可能出填空判断选择等小题）
5. 3型文法是正规文法、正则文法、线性文法（用于词法分析） 6. 2型文法也称为上下文无关文法（用于语法分析） 7. 1型文法也称为上下文有关文法
若一个文法是递归的，则由它产生的语言的句子个数是无限的。
（2）自上而下 8. 文法左递归的定义
一个文法中如果存在某个产生式 P→Pα（即有某个侯选式的最左边的符号是这个产生式左部非终结符本身），则此文法是有左递归的。
9. 消除文法的左递归的方法：
只要求消除直接左递归，方法见下面的例子。 设有产生式
P→Pα|β P→βP’ P’→αP’|ε
其中β不以P开头，α不为ε，那么，我们可以把P的规则改为如下的非直接左递归形式：
这样就消除了P→Pα|β这个式子的左递归。
（提示：在做题时，要把整个文法的每个产生式都逐一检验，有时含有左递归的产生式是不只一个的，需要逐个消除。）
10.First集合Follow集的构造方法（较抽象）
First集的构造方法：
对于任意一个符号X，构造他的frist集的方法是：
(1)若X∈VT （终结符），则FIRST(X)={X}.
(2)若X∈VN（非终结符），且有产生式X→a…（小写a代表任意一个终结符号，他是侯
选式左边的第一个字符），则把a加入到FIRST(X)中；若X→ε也是一条产生式，则把ε也加到FIRST(X)中。
若有产生式X→Y…（大写Y代表任意一个非终结符号，他是侯选式左边的第一个字符），
相关推荐：
loading