出版日期：2004-1-19　　总期号：553　本年期号：03

本期导读 综合报道 软件与应用 硬件世界 整机与数码 网络与通信　 游戏天地 教育信息化 读者俱乐部

软件水平考试备考宝典 编译原理篇（三） 《中国电脑教育报》刘靓 　　上期我们介绍了两道例题，最后我们来看看有关状态图的知识点和一道2002年的试题分析。 　　三、状态图 　　每一个节点表示一个状态，边上的权表示一个输入，当输入一个字符后，将从一个状态变换到另一个状态。如果权为ε，ε为空符，则表示输入空符，前后状态不变。如： 　　节点1、2、3分别表示状态1、2和3，开始状态为状态2（有箭头指向），状态2输入1后变为状态3（结束状态，有双圆），状态2输入ε变为状态1，状态不变，即状态2和状态1相等，那么状态1也为开始状态。状态1输入1后变为状态3，状态3输入0后变为状态1。 　　子集法将NFA变换为DFA，就是将开始状态集合中的每个节点状态输入某个字符后所变换得到的状态所组成了一个新的状态集合，再以这个状态集合为新的起始状态集合，求这个状态集合中的每个节点状态输入某个字符后所变换得到的状态所组成的新的状态集合，依次下去，直到求完所有的状态集合。 　　例3：2002年试题 　　已知一不确定的有穷自动机（NFA）如下图所示，采用子集法将其确定化为DFA的过程如下表示。 　　状态集T1中不包括编号为 (1) 的状态；状态集T2中的成员有 (2) ；状态集T3等于 (3) ；该自动机所识别的语言可以用正规式 (4) 表示。 　　与正规式 (alb)�� 等价的正规式为 (5) 。 　　解答过程： 　　S为初始状态，1、2、3状态和s状态相等，则I中第一个集合为{S，1，2，3 }。S状态输入0无状态存在；1状态输入0后还是1状态，和1状态相等的有3状态，故1状态输入0后变为1状态和3状态；2状态输入0后无状态，3状态输入0后变为4，5和z状态，故I0的第一个状态集合为{1，3，4，5，Z}。 　　又S状态输入1无状态存在，1状态输入1后无状态；2状态输入1后还是2状态，和2状态相等的有3状态，故2状态输入1后变为2状态和3状态；3状态输入1后无状态。故I1的第一个状态集合为{2，3}，依次I的第二个状态集合选择I0的第一个状态集合为{1，3，4，5，Z}，重复上述步骤，直到所有的状态集合都进行了输入变换。 　　|为或者，�澅硎疚尴薅喔觥� 　　（a|b）�澅硎居蒩和b组成的所有字符串，如a、b、aa、ab、bb、ba………。 　　a�澅硎居衋组成的任一字符串。 　　上图所表示的字符串用正则表达式表示为：（a�潀b�潱�0（01）�潯� 　　因此，正确答案为ADDDC。 　　有关编译原理的复习我们就介绍到这里，大家有什么疑问和要求，可以来信与我们交流training＠cce．com．cn。