精华内容
下载资源
问答
  • 有穷自动机有穷自动机的化简与确定代码报告及PPT的化简与确定 编译原理课程设计 C++
  • 3.4.4 确定有穷自动机的化简 1.化简的有穷自动机的定义 一个没有多余状态并且没有两个状态是等价的有穷自动机。 多余状态(无用状态):从该自动机的开始状态出发,任何输入串也不能到达的那个状态 等价状态: 两个...

    3.4.4 确定有穷自动机的化简

    1.化简的有穷自动机的定义

    一个没有多余状态并且没有两个状态是等价的有穷自动机。

    多余状态(无用状态):从该自动机的开始状态出发,任何输入串也不能到达的那个状态

    等价状态:

    1. 两个状态必须同时为可接受状态(终态)或者不可接受状态(非终态)——一致性条件
    2. 对于所有的输入符号,两个状态接受相同的符号必须转换到等价的状态——蔓延性条件

    2.分割法

    在这里插入图片描述

    我们首先将其分为终态和非终态

    在这里插入图片描述

    P0P_0 = ({1, 2, 3, 4}, {5, 6, 7})

    接下来我们尝试先对{1, 2, 3, 4}这个子集进行划分

    1a61\stackrel{a}{\longrightarrow}61b31\stackrel{b}{\longrightarrow}3

    2a72\stackrel{a}{\longrightarrow}72b32\stackrel{b}{\longrightarrow}3

    3a13\stackrel{a}{\longrightarrow}13b53\stackrel{b}{\longrightarrow}5

    4a44\stackrel{a}{\longrightarrow}44b64\stackrel{b}{\longrightarrow}6

    首先我们看如果输入a的话,1和2的输出为{5,6,7}这个集合中的元素,而3和4则仍是本集合的元素,所以根据等价状态的第二性质,我们可以将1、2 与3、4分割开。

    在这里插入图片描述

    P1P_1 = ({1, 2}, {3, 4}, {5, 6, 7})

    对于目前这个新的集合来说,我们继续划分每个子集。首先从{1,2}开始

    1a61\stackrel{a}{\longrightarrow}61b31\stackrel{b}{\longrightarrow}3

    2a72\stackrel{a}{\longrightarrow}72b32\stackrel{b}{\longrightarrow}3

    我们无论是对1,2输入a还是输入b,它们的输出都属于同一个集合——6、7属于{5,6,7}这个终态集合,3属于{3,4}这个集合,所以{1,2}这个集合很完美,无法划分(即状态无法区分),它俩好得跟一个人似的。

    在这里插入图片描述

    那么我们继续看{3,4}

    3a13\stackrel{a}{\longrightarrow}13b53\stackrel{b}{\longrightarrow}5

    4a44\stackrel{a}{\longrightarrow}44b64\stackrel{b}{\longrightarrow}6

    哦,我们看到,当输入a的时候,3输出的是1,属于{1,2}集合;4则输出的是4,属于{3,4}集合,所以3和4的状态可区分。

    在这里插入图片描述

    那么更新我们的状态图

    在这里插入图片描述

    更新P

    P2P_2 = ({1,2}, {3}, {4}, {5, 6, 7})

    很明显我们的故事还没结束,还有{5,6,7}这个集合

    5a75\stackrel{a}{\longrightarrow}75b35\stackrel{b}{\longrightarrow}3

    6a46\stackrel{a}{\longrightarrow}46b16\stackrel{b}{\longrightarrow}1

    7a47\stackrel{a}{\longrightarrow}47b27\stackrel{b}{\longrightarrow}2

    很明显,在输入a的时候,5的输出为7即{5,6,7} 本集合内的,而6、7则是输出的同一个集合。二话不说,分家!

    在这里插入图片描述

    P3P_3 = ({1,2}, {3}, {4}, {5}, {6, 7})

    这时候,还剩{6,7},如果你上面看明白了,那么到这里你也就懂了,6、7是不可区分的状态。

    分割法到此结束……

    ……不还有最后一步,把所有的不可区分状态统统用其中一个状态来表示就行。

    比如1、2,我们直接用1来代替就行,把2所有的输入和输出的压力都放到1身上

    在这里插入图片描述

    1b31\stackrel{b}{\longrightarrow}32b32\stackrel{b}{\longrightarrow}3 所以这两个线用一个就行)

    然后我们发现6、7可以直接用6代替

    在这里插入图片描述

    把虚线收拾干净再看看

    在这里插入图片描述

    在这里插入图片描述

    3.The End

    在这里插入图片描述

    展开全文
  • (1) 正规式到DFA转化; (2) NFA到DFA转化; (3) DFA最小化; (4) 对输入字符测试。
  • 有穷自动机的每一步操作都是确定的,因此可称为确定型有穷自动机。确定有穷自动机就是说当一个状态面对一个输入符号的时候,它所转换到的是一个唯一确定的状态。 表示 例子 那么可以根据上面的5元组,绘制出下面...

    DFA:deterministic finite automator

    介绍

    概念:

    有穷自动机的每一步操作都是确定的,因此可称为确定型有穷自动机。确定有穷自动机就是说当一个状态面对一个输入符号的时候,它所转换到的是一个唯一确定的状态。

    表示

    在这里插入图片描述

    例子

    在这里插入图片描述
    那么可以根据上面的5元组,绘制出下面的状态转移图。
    解释:q0,q1,q2都是状态,所以都是节点,其中q0是开始状态,q1是终止状态(我打了两个圈)。{0,1}表示输入串中允许出现的符号,比如给你的可能是001010等等。而δ(q0,0)=q0\delta(q_0,0)=q_0表示当你当前处于状态q0时,如果输入串给了你一个输入符号0,那么请你转移到状态q0。
    在这里插入图片描述
    我们试一下这个DFA是否可以接受这样的符号串0111。我们按照转移函数一个个走就行了,注意初始状态是q0,符号串的第一个符号是0。
    即:
    当前状态:q0
    当前输入符号:0
    剩余符号:111
    所以:
    在这里插入图片描述
    即:
    当前状态:q0
    当前输入符号:1
    剩余符号:11
    接下来依次类推,最终有:
    在这里插入图片描述
    从而最终进入了终态,q1。也就是说0111将被这个DFA接受,但是如果你提供了一个字符串0010,你会发现DFA不会接受。

    化简

    为什么需要化简?
    例子:
    化简类型1,删除无用状态,例如下面的q2是不可能从初始状态q0到达的,所以没有用
    在这里插入图片描述
    化简类型2
    注:q0是开始,q1是结束
    在这里插入图片描述
    容易看出来这个DFA是接受形如01的符号串,0表示0可以出现任意多次,包括0次。
    我们再看下一个;
    在这里插入图片描述
    我们发现,上面这个DFA也是接受0*1,也就是说这两个DFA功能一样,接受一样的语言,但是定义却不一样,我们希望找到一个方法,来选择简单的那个DFA,比如这里的第一个DFA,其状态更少,更加简洁。
    在这里插入图片描述
    如何化简?
    分割法:
    为了简单起见,我们以上面的DFA2为例,大概走一个流程即好。
    步骤1,对所有状态进行切分,先划分为两个集合,这样划分的原因是,这两种类型的状态一定是不一样的,也就是一定是可以区分的

    I0 = {q0,q2} ; 非终态
    
    I1 = {q1} ; 终态
    
    

    步骤2,对I0,I1状态继续进行切分,至于能不能继续切分我们不知道,但是要试一下,I1就不用切分了,因为里面只有一个状态,不可能可以分成两个集合。
    但是I0里面有两个状态,可能是可区分的,我们得试一试,如何试一试?方法如下:

    move(q0,0) = q2 ∈I0
    
    move(q0,1) = q1 ∈I1
    
    move(q2,0) = q2 ∈I0
    
    move(q2,1) = q1 ∈I1
    
    
    可以发现,q0,q1是等价的.
    
    

    解释,上面的move就是那个转移函数δ\delta。然后,我们还发现q0,q1读入一个0都转移到了I0(注意,现在我们的视角要上升到我们之前划分的集合I0,I1了。)q0,q1读入一个1都转移到了I1,所以q0,q1完全相同,不需要再进行拆分!也就是说最终的状态集合变成了I0,I1。
    那么根据DFA的定义,我们还需要转移函数啊?哪来?
    注意到I0里面的任意元素都是等价的,所以你可以随便找上面的转移函数拿来用,比如根据上面的move有:

    move(q0,0) = I0
    
    move(q0,1) = I1
    

    改成:

    move(I0,0) = I0
    
    move(I0,1) = I1
    

    从而最终就是:
    在这里插入图片描述
    至此我们的化简就结束了。

    例子2

    假设有如下DFA,试着将其最小化。
    在这里插入图片描述
    分割成I0,I1

    I0 = {1,2,3,4} ; 非终态
    
    I1 = {5,6,7} ; 终态
    
    

    检验I0中元素的等价性,不等价就分割

    move(1,a) = 6 ∈I1
    
    move(1,b) = 3 ∈I0
    
    move(2,a) = 7 ∈I1
    
    move(2,b) = 3 ∈I0
    
    move(3,a) = 1 ∈I0
    
    move(3,b) = 5 ∈I1
    
    move(4,a) = 4 ∈I0
    
    move(4,b) = 6 ∈I1
    
    可以发现,{1,2}是等价的,{3,4}是等价的
    
    

    所以现在分割成了:I2 = {1,2}, I1 = {5,6,7}, I3 = {3,4},注意I0已经不复存在了,现在只有这3个状态集合。
    检测I2中元素的等价性,不等价就分割

    move(1,a) = 6 ∈I1
    
    move(1,b) = 3 ∈I3
    
    move(2,a) = 7 ∈I1
    
    move(2,b) = 3 ∈I3
    
    可以发现,是等价的,不用分割
    
    

    检测I3中元素的等价性,不等价就分割

    move(3,a) = 1 ∈I2
    
    move(3,b) = 5 ∈I1
    
    move(4,a) = 4 ∈I3
    
    move(4,b) = 6 ∈I1
    可以发现,不是等价的,分割成{3},{4}
    
    

    所以现在分割成了:I2 = {1,2}, I1 = {5,6,7}, I4 = {3}, I5 = {4}
    检测I1中元素的等价性,不等价就分割

    move(5,a)  = 7 ∈ I1
    move(5,b)  = 3 ∈ I4
    
    move(6,a)  = 4 ∈ I5
    move(6,b)  = 1 ∈ I2
    
    move(7,a)  = 4 ∈ I5
    move(7,b)  = 2 ∈ I2
    
    可以发现,不是等价的,分割成{6,7}, {5}
    
    

    所以现在分割成了:I2 = {1,2}, I4 = {3}, I5 = {4}, I6 = {5},I7 = {6,7}

    检测后发现,不可再分割,所以最终分割结果就是:I2 = {1,2}, I4 = {3}, I5 = {4}, I6 = {5},I7 = {6,7}
    最终结果为:
    在这里插入图片描述
    注意顶点的名字随便取。上面是1,3,4,5,6完全也可以是其他的不同符号,予以区别就行。

    应用

    DFA的应用是和正则文法的等价性,和正则表达式也是等价的,所以可能用来分析一个给定的输入串是否合法,可以用于编译前端的词法分析:比如分析一个变量的名字是否为合法的标识符,假设有一种编程语言要求:变量命名必须开头是字母,后面是字母或者数字。那么可以有如下DFA来帮助我们识别用户的命名是否合法:
    在这里插入图片描述
    其中letter表示字母,可以大小写,digit表示一个数字。

    展开全文
  • 通过设计、编写和调试将确定的有穷自动机的状态数变为最少的C程序,使得学生掌握化简有穷自动机的过程中的相关概念和方法。DFA的表现形式可以为表格或图形。 二、 实验内容 每一个正规集都可以由一个状态数最少的...

    一、 实验目的

    通过设计、编写和调试将确定的有穷自动机的状态数变为最少的C程序,使得学生掌握化简为有穷自动机的过程中的相关概念和方法。DFA的表现形式可以为表格或图形。

    二、 实验内容

    每一个正规集都可以由一个状态数最少的DFA所识别,这个DFA是唯一的(不考虑同构的情况)。任意给定的一个DFA,根据以下算法设计一个C程序,将该DFA 化简为与之等价的最简DFA。

    三、 实验环境

    供Windows7系统下的PC机,DEV C++软件,语言:C++。

    四、 算法与实验原理

    (1)构造具有两个组的状态集合的初始划分I:接受状态组 F 和非接受状态组 Non-F。

    (2)对I采用下面所述的过程来构造新的划分I-new.

     For I 中每个组G  do  
            Begin  
             当且仅当对任意输入符号a,状态s和读入a后转换到I的同一组中
    	/*最坏情况下,一个状态就可能成为一个组*/  
    	           用所有新形成的小组集代替I-new中的G;  
    	     end  
    

    (3)如果I-new=I,令I-final=I,再执行第(4)步,否则令I=I=new,重复步骤(2)。

    (4)在划分I-final的每个状态组中选一个状态作为该组的代表。这些代表构成了化简后的DFA M'状态。令s是一个代表状态,而且假设:在DFA M中,输入为a时有从s到t转换。令t所在组的代表是r,那么在M’中有一个从s到r的转换,标记为a。令包含s0的状态组的代表是M’的开始状态,并令M’的接受状态是那些属于F的状态所在组的代表。注意,I-final的每个组或者仅含F中的状态,或者不含F中的状态。

    (5)如果M’含有死状态(即一个对所有输入符号都有刀自身的转换的非接受状态d),则从M’中去掉它;删除从开始状态不可到达的状态;取消从任何其他状态到死状态的转换。

    (6)实现的数据结构:

    1.	用链表实现DFA的构造:由结点链表和转换弧链表组成:  
    2.	  struct node //结点的定义  
    3.	{int pos;//结点在哪个组中  
    4.	 int num;//结点的序号  
    5.	 int accept; //结点是否为接受状态  
    6.	 struct node *next;    
    7.	}NODE;  
    8.	        struct arc//弧的定义  
    9.	          {int start;  //开始的顶点位置  
    10.	           char input;  //弧上所接受的输入字符  
    11.	           int end;   //结束的顶点位置  
    12.	           struct arc *next;  
    13.	}ARC;  
    14.	        Struct groups  //分组后各结点所在组的位置  
    15.	         {int n; //属于哪个组  
    16.	          int i;//在组中的位置  
    17.	}GROUPs;  
    

    (7)实现方法:
    根据accept的值为0还是1进行初次划分I,将accept为0的所有结点构建成一个链表,将accept为1的所有结点构建一个链表。然后执行最小化函数,对每一个输入字符遍历以上个链表,对每个结点.num=弧.start的情况,查看该弧.end的组号是否相等,相等则不划分;若不相等,则需进一步划分,构建新的链表等。
    划分完成后选头结点为代表,删除结点链表上其他结点,并将弧线链表上需被删的弧.start或弧.end该为头结点。

    五、 实验代码

    1.	#include<stdio.h>  
    2.	#include<iostream>  
    3.	#include<cstring>  
    4.	#define MAX 1111  
    5.	  
    6.	using namespace std;  
    7.	  
    8.	struct state_transition{  
    9.	    char start_point;  
    10.	    char edge;  
    11.	    char end_point;  
    12.	};  
    13.	  
    14.	//求集合的差  
    15.	void subset(char *s1,char *s2,char *s)  
    16.	{  
    17.	    int len1 = strlen(s1);  
    18.	    int len2 = strlen(s2);  
    19.	    for(int i=0,j=0,cnt=0; i<len1; i++,j=0){  
    20.	        for(; j<len2; j++){  
    21.	            if(s1[i]==s2[j]) break;  
    22.	        }  
    23.	        if(j>=len2){  
    24.	            s[cnt++] = s1[i];  
    25.	        }  
    26.	    }  
    27.	}  
    28.	  
    29.	//判断下一个状态属于哪个集合  
    30.	int jude_set(char result[MAX][MAX],int rlen,char ch1,char ch2,state_transition *dfam,int tlen)  
    31.	{  
    32.	  
    33.	    for(int i=0; i<tlen; i++){  
    34.	        if(ch1 == dfam[i].start_point && ch2 == dfam[i].edge){  
    35.	            for(int t=0; t<rlen; t++){  
    36.	                for(int j=0; j<strlen(result[t]); j++){  
    37.	                    if(dfam[i].end_point==result[t][j]){  
    38.	                        return t;  
    39.	                    }  
    40.	                }  
    41.	            }  
    42.	        }  
    43.	    }  
    44.	    return -1;  
    45.	}  
    46.	  
    47.	  
    48.	int main()  
    49.	{  
    50.	    state_transition DFAM[MAX];  
    51.	    char state[MAX];  
    52.	    char finaly[MAX];  
    53.	    char s[MAX];  
    54.	    char result[MAX][MAX];  
    55.	    int cnt = 0;  
    56.	    char ch;  
    57.	    //输入总共的状态集  
    58.	    cout<<"请输入DFAM的总状态(各状态之间用空格隔开结尾用#结束)"<<endl;  
    59.	    while(true){  
    60.	        cin>>ch;  
    61.	        if(ch == '#') break;  
    62.	        state[cnt++] = ch;  
    63.	    }  
    64.	    //输入终态集  
    65.	    cout<<"请输入DFAM的终态(各状态之间用空格隔开结尾用#结束)"<<endl;  
    66.	    cnt = 0;  
    67.	    while(true){  
    68.	        cin>>ch;  
    69.	        if(ch == '#') break;  
    70.	        finaly[cnt++] = ch;  
    71.	    }  
    72.	    //输入状态关系  
    73.	    cnt = 0;  
    74.	    while(true){  
    75.	        cin>>DFAM[cnt].start_point>>DFAM[cnt].edge>>DFAM[cnt].end_point;  
    76.	        if(DFAM[cnt].start_point=='#' && DFAM[cnt].edge=='#' && DFAM[cnt].end_point=='#')  
    77.	            break;  
    78.	        cnt++;  
    79.	    }  
    80.	  
    81.	    //把总状态分为终态与非终态。  
    82.	    subset(state,finaly,s);  
    83.	    strcpy(result[0],s);  
    84.	  
    85.	    //核心算法  
    86.	    int set_count = 1;  
    87.	    while(true){  
    88.	        bool flag = false;  
    89.	        int t1,t2;  
    90.	        t1 = jude_set(result,set_count,result[set_count-1][0],'a',DFAM,cnt);  
    91.	        t2 = jude_set(result,set_count,result[set_count-1][0],'b',DFAM,cnt);  
    92.	        //printf("t1 t2:%d %d\n",t1,t2);  
    93.	        char temp[MAX]={result[set_count-1][0]};  
    94.	        //printf("temp:%s\n",temp);  
    95.	        //printf("strlen(s):%d\n",strlen(s));  
    96.	        for(int j=1,c=0; j<strlen(result[set_count-1]); j++){  
    97.	            if(t1==jude_set(result,set_count,result[set_count-1][j],'a',DFAM,cnt) &&  
    98.	               t2==jude_set(result,set_count,result[set_count-1][j],'b',DFAM,cnt)){  
    99.	                //printf("s[j]:%c\n",result[set_count-1][j]);  
    100.	                temp[++c] = result[set_count-1][j];  
    101.	            }  
    102.	            else flag = true;  
    103.	        }  
    104.	        if(flag){  
    105.	            char temp1[MAX]="";  
    106.	            subset(result[set_count-1],temp,temp1);  
    107.	            strcpy(result[set_count-1],temp);  
    108.	            strcpy(result[set_count++],temp1);  
    109.	            //printf("result temp temp1:%s %s %s\n",result[set_count-1],temp,temp1);  
    110.	        }  
    111.	        else break;  
    112.	    }  
    113.	    //核心算法  
    114.	    strcpy(result[set_count++],finaly);  
    115.	    while(true){  
    116.	        bool flag = false;  
    117.	        int t1,t2;  
    118.	        t1 = jude_set(result,set_count,result[set_count-1][0],'a',DFAM,cnt);  
    119.	        t2 = jude_set(result,set_count,result[set_count-1][0],'b',DFAM,cnt);  
    120.	        //printf("t1 t2:%d %d\n",t1,t2);  
    121.	        char temp[MAX]={result[set_count-1][0]};  
    122.	        //printf("temp:%s\n",temp);  
    123.	        //printf("strlen(s):%d\n",strlen(s));  
    124.	        for(int j=1,c=0; j<strlen(result[set_count-1]); j++){  
    125.	            if(t1==jude_set(result,set_count,result[set_count-1][j],'a',DFAM,cnt) &&  
    126.	               t2==jude_set(result,set_count,result[set_count-1][j],'b',DFAM,cnt)){  
    127.	                //printf("s[j]:%c\n",result[set_count-1][j]);  
    128.	                temp[++c] = result[set_count-1][j];  
    129.	            }  
    130.	            else flag = true;  
    131.	        }  
    132.	        if(flag){  
    133.	            char temp1[MAX]="";  
    134.	            subset(result[set_count-1],temp,temp1);  
    135.	            strcpy(result[set_count-1],temp);  
    136.	            strcpy(result[set_count++],temp1);  
    137.	        }  
    138.	        else break;  
    139.	    }  
    140.	  
    141.	    cout<<"化简后的DFAM'新状态如下:"<<endl;  
    142.	    for(int i=0,jj,len; i<set_count; i++){  
    143.	        len = strlen(finaly);  
    144.	        for(jj=0; jj<len; jj++){  
    145.	            if(result[i][0]==finaly[jj]) break;  
    146.	        }  
    147.	        if(jj>=len) cout<<"普通状态"<<i<<"(";  
    148.	        else cout<<"终态"<<i<<"(";  
    149.	        int j = 0;  
    150.	        for(; j<strlen(result[i])-1; j++){  
    151.	            cout<<result[i][j]<<",";  
    152.	        }  
    153.	        printf("%c)\n",result[i][j]);  
    154.	    }  
    155.	    cout<<"化简后的DFAM'各状态关系如下:"<<endl;  
    156.	    for(int i=0; i<set_count; i++){  
    157.	        if(jude_set(result,set_count,result[i][0],'a',DFAM,cnt)!=-1)  
    158.	            cout<<i<<" a "<<jude_set(result,set_count,result[i][0],'a',DFAM,cnt)<<endl;  
    159.	        if(jude_set(result,set_count,result[i][0],'b',DFAM,cnt)!=-1)  
    160.	            cout<<i<<" b "<<jude_set(result,set_count,result[i][0],'b',DFAM,cnt)<<endl;  
    161.	    }  
    162.	    return 0;  
    163.	}  
    

    六、 实验结论

    输入下图的DFA M,得到其最简的DFA M’。
    在这里插入图片描述

    代码运行结果:
    在这里插入图片描述

    结果描述:
    (1)键盘输入:

    1.	/* 
    2.	0 1 2 3 4 5 6 # 
    3.	3 4 5 6 # 
    4.	0 a 1 
    5.	0 b 2 
    6.	1 a 3 
    7.	1 b 2 
    8.	2 a 1 
    9.	2 b 4 
    10.	3 a 3 
    11.	3 b 5 
    12.	4 a 6 
    13.	4 b 4 
    14.	5 a 6 
    15.	5 b 4 
    16.	6 a 3 
    17.	6 b 5 
    18.	# # # 
    19.	*/  
    

    (2)结果描述
    首先输入的是 DFA M状态图的状态,然后输入终态,默认第一个数为初态。
    通过邻接矩阵来存储状态图之间的关系,代码如下:

    1.	while(true){  
    2.	    cin>>DFAM[cnt].start_point>>DFAM[cnt].edge>>DFAM[cnt].end_point;  
    3.	    if(DFAM[cnt].start_point=='#' && DFAM[cnt].edge=='#' && DFAM[cnt].end_point=='#')  
    4.	        break;  
    5.	    cnt++;  
    6.	} 
    

    采用“分割法”与“子集法”来把一个DFA(不含多余状态)的状态分成一些不相交的子集,使得任何两个不同的子集都是可区别的,而同一子集中的任何两个状态都是等价的。在有穷自动机中,两个状态s和t 不等价的条件:
    ① 一致性条件——状态s 和t必须同时为可接受状态或不可接受状态。
    ② 蔓延性条件——对于所有输入符号,状态s和状态t必须转换到等价的状态里。
    代码描述如下:

    1.	//判断下一个状态属于哪个集合  
    2.	int jude_set(char result[MAX][MAX],int rlen,char ch1,char ch2,state_transition *dfam,int tlen)  
    3.	{  
    4.	  
    5.	    for(int i=0; i<tlen; i++){  
    6.	        if(ch1 == dfam[i].start_point && ch2 == dfam[i].edge){  
    7.	            for(int t=0; t<rlen; t++){  
    8.	                for(int j=0; j<strlen(result[t]); j++){  
    9.	                    if(dfam[i].end_point==result[t][j]){  
    10.	                        return t;  
    11.	                    }  
    12.	                }  
    13.	            }  
    14.	        }  
    15.	    }  
    16.	    return -1;  
    17.	} 
    

    (3)DFA M最小化(此部分代码为网上代码)步骤描述:
    ① 对于DFA的字母表M,把M划分成终态集和非终态集,令P=M。
    ② 对于P中的一个集合I,寻找I每一个元素K,找到K从边a对应的节点,加入集合I1,若I1是P中某个集合的子集,跳至步骤3,若不是,步骤4.
    ③ 寻找P中下一个集合,执行步骤2,若所有集合均是子集,则步骤5.
    ④ 将I1划分成P中某几个集合子集的形式,将I1划分后的集合加入P,并删除I。执行步骤3。

    1.	 int set_count = 1;  
    2.	 while(true){  
    3.	     bool flag = false;  
    4.	     int t1,t2;  
    5.	     t1 = jude_set(result,set_count,result[set_count-1][0],'a',DFAM,cnt);  
    6.	     t2 = jude_set(result,set_count,result[set_count-1][0],'b',DFAM,cnt);  
    7.	     //printf("t1 t2:%d %d\n",t1,t2);  
    8.	     char temp[MAX]={result[set_count-1][0]};  
    9.	     //printf("temp:%s\n",temp);  
    10.	     //printf("strlen(s):%d\n",strlen(s));  
    11.	     for(int j=1,c=0; j<strlen(result[set_count-1]); j++){  
    12.	         if(t1==jude_set(result,set_count,result[set_count-1][j],'a',DFAM,cnt) &&  
    13.	            t2==jude_set(result,set_count,result[set_count-1][j],'b',DFAM,cnt)){  
    14.	             //printf("s[j]:%c\n",result[set_count-1][j]);  
    15.	             temp[++c] = result[set_count-1][j];  
    16.	         }  
    17.	         else flag = true;  
    18.	     }  
    19.	     if(flag){  
    20.	         char temp1[MAX]="";  
    21.	         subset(result[set_count-1],temp,temp1);  
    22.	         strcpy(result[set_count-1],temp);  
    23.	         strcpy(result[set_count++],temp1);  
    24.	         //printf("result temp temp1:%s %s %s\n",result[set_count-1],temp,temp1);  
    25.	     }  
    26.	     else break;  
    27.	 }  
    28.	 //核心算法  
    29.	 strcpy(result[set_count++],finaly);  
    30.	 while(true){  
    31.	     bool flag = false;  
    32.	     int t1,t2;  
    33.	     t1 = jude_set(result,set_count,result[set_count-1][0],'a',DFAM,cnt);  
    34.	     t2 = jude_set(result,set_count,result[set_count-1][0],'b',DFAM,cnt);  
    35.	     //printf("t1 t2:%d %d\n",t1,t2);  
    36.	     char temp[MAX]={result[set_count-1][0]};  
    37.	     //printf("temp:%s\n",temp);  
    38.	     //printf("strlen(s):%d\n",strlen(s));  
    39.	     for(int j=1,c=0; j<strlen(result[set_count-1]); j++){  
    40.	         if(t1==jude_set(result,set_count,result[set_count-1][j],'a',DFAM,cnt) &&  
    41.	            t2==jude_set(result,set_count,result[set_count-1][j],'b',DFAM,cnt)){  
    42.	             //printf("s[j]:%c\n",result[set_count-1][j]);  
    43.	             temp[++c] = result[set_count-1][j];  
    44.	         }  
    45.	         else flag = true;  
    46.	     }  
    47.	     if(flag){  
    48.	         char temp1[MAX]="";  
    49.	         subset(result[set_count-1],temp,temp1);  
    50.	         strcpy(result[set_count-1],temp);  
    51.	         strcpy(result[set_count++],temp1);  
    52.	     }  
    53.	     else break;  
    54.	 }  
    

    七、 实验遇到的问题

    问题描述:在实验室,我自己写的代码只能实现实例的输入情况,因为没有具体的子集法相关代码,所以采用的是枚举法,暴力求解了这一关题,实现效率非常低,而且无法处理其他情况。
    问题解决方法:通过上网查询以及询问同学,结合大家的代码,才得以实现,但是我仍然有许多地方不大明白,这是此次实验的最大不足之处。代码如下:

    1.	strcpy(result[set_count++],finaly);  
    2.	    while(true){  
    3.	        bool flag = false;  
    4.	        int t1,t2;  
    5.	        t1 = jude_set(result,set_count,result[set_count-1][0],'a',DFAM,cnt);  
    6.	        t2 = jude_set(result,set_count,result[set_count-1][0],'b',DFAM,cnt);  
    7.	        //printf("t1 t2:%d %d\n",t1,t2);  
    8.	        char temp[MAX]={result[set_count-1][0]};  
    9.	        //printf("temp:%s\n",temp);  
    10.	        //printf("strlen(s):%d\n",strlen(s));  
    11.	        for(int j=1,c=0; j<strlen(result[set_count-1]); j++){  
    12.	            if(t1==jude_set(result,set_count,result[set_count-1][j],'a',DFAM,cnt) &&  
    13.	               t2==jude_set(result,set_count,result[set_count-1][j],'b',DFAM,cnt)){  
    14.	                //printf("s[j]:%c\n",result[set_count-1][j]);  
    15.	                temp[++c] = result[set_count-1][j];  
    16.	            }  
    17.	            else flag = true;  
    18.	        }  
    19.	        if(flag){  
    20.	            char temp1[MAX]="";  
    21.	            subset(result[set_count-1],temp,temp1);  
    22.	            strcpy(result[set_count-1],temp);  
    23.	            strcpy(result[set_count++],temp1);  
    24.	        }  
    25.	        else break;  
    

    八、 实验心得

    通过实验我进一步明白了子集法的用法以及如何实现,可以根据accept的值为0还是1进行初次划分I,将accept为0的所有结点构建成一个链表,将accept为1的所有结点构建一个链表。然后执行最小化函数,对每一个输入字符遍历以上个链表,对每个结点.num=弧.start的情况,查看该弧.end的组号是否相等,相等则不划分;若不相等,则需进一步划分,构建新的链表等。划分完成后选头结点为代表,删除结点链表上其他结点,并将弧线链表上需被删的弧.start或弧.end该为头结点。
    在实验过程遇到了许多问题,同时也发现了自己的编程能力不行,很多数据结构方面的知识点都忘记了,我自己写的代码不能实现DFA最小化,实验报告的代码是和同学讨论以及上网查资料写出来的,通过实验我明白了编程的重要性,学好这门学科需要扎实的编程基础以及强大的逻辑思维,应学会灵活的运用数据结构。

    展开全文
  • 任意给定一个DFA,根据以下算法设计一个C程序,将该DFA 化简为与之等价最简DFA。 2. 实验设计分析 2.1 实验设计思路 根据实验指导书和书本上相关知识,实现算法。 2.2 实验算法 (1)构造具有两个组状态...
  • 确定有穷自动机(DFA)化简(最小化)

    万次阅读 多人点赞 2018-04-27 11:35:12
    一个DFA可以通过消除无用状态、合并等价状态而转换成一个与之等价最小状态的有穷自动机。 无用状态:从自动机开始状态出发,任何输入串也发到达那个状态,或者这个状态没有通路可达终态。 等价转态:两个状态,...

    预备

    • 最简化的DFA:这个DFA没有多余状态、也没有两个相互等价的状态。一个DFA可以通过消除无用状态合并等价状态而转换成一个与之等价的最小状态的有穷自动机。
    • 无用状态:从自动机开始状态出发,任何输入串也发到达的那个状态,或者这个状态没有通路可达终态。
    • 等价转态:两个状态,识别相同的串,结果都同为正确或错误,这两个状态就是等价的。
    • 区别状态:不是等价状态。

    化简DFA

    • 分割法:把一个DFA(不含多余状态)的状态分割成一些不相交的子集,并且任意两个子集之间的状态都是可区别状态,同一子集内部的状态都是等价状态。

    • 步骤(按分割法)

      • I0 = 非状态元素构成的集合,I1 = 终态元素构成的集合
      • 经过多次划分后,要保证,任意一个Ik中的元素通过move(Ik,某个字符)的结果都同属于一个Iz,这时候划分完成。否则把状态不同的单独划分出去。
      • 重复上一步,直至没有新的I子集增加。
      • 从子集中任选一个代替整体,画出最简DFA。

    例子

    • 题目:将下图DFA M最小化

    微信公众号:JavaWeb架构师

    • 分割成I0,I1
    -----------------I0、I1分割-------------------
    I0 = {1,2,3,4} ; 非终态
    I1 = {5,6,7} ; 终态
    • 检验I0中元素的等价性,不等价就分割
    move(1,a) = 6 ∈I1
    move(1,b) = 3 ∈I0
    
    move(2,a) = 7 ∈I1
    move(2,b) = 3 ∈I0
    
    move(3,a) = 1 ∈I0
    move(3,b) = 5 ∈I1
    
    move(4,a) = 4 ∈I0
    move(4,b) = 6 ∈I1
    
    可以发现,{1,2}是等价的,{3,4}是等价的
    所以现在分割成了:I2 = {1,2}, I1 = {5,6,7}, I3 = {3,4}
    • 检测I2中元素的等价性,不等价就分割
    move(1,a) = 6 ∈I1
    move(1,b) = 3 ∈I3
    
    move(2,a) = 7 ∈I1
    move(2,b) = 3 ∈I3
    
    可以发现,是等价的,不用分割
    • 检测I3中元素的等价性,不等价就分割
    move(3,a) = 1 ∈I2
    move(3,b) = 5 ∈I1
    
    move(4,a) = 4 ∈I3
    move(4,b) = 6 ∈I1
    可以发现,不是等价的,分割成{3},{4}
    所以现在分割成了:I2 = {1,2}, I1 = {5,6,7}, I4 = {3}, I5 = {4}
    • 检测I1中元素的等价性,不等价就分割
    move(5,a)  = 7 ∈ I1
    move(5,b)  = 3 ∈ I4
    
    move(6,a)  = 4 ∈ I5
    move(6,b)  = 1 ∈ I2
    
    move(7,a)  = 4 ∈ I5
    move(7,b)  = 2 ∈ I2
    
    可以发现,不是等价的,分割成{6,7}, {5}
    所以现在分割成了:I2 = {1,2}, I4 = {3}, I5 = {4}, I6 = {5},I7 = {6,7} 
    • 检测后发现,不可再分割,所以最终分割结果就是:I2 = {1,2}, I4 = {3}, I5 = {4}, I6 = {5},I7 = {6,7}

    • 画转态转换图:从集合中选取一个代表就可以
      微信公众号:JavaWeb架构师

    其它

    课件下载:

    关注下方微信公众号,
    回复:
    DFA化简.code

    完整教程PDF版本下载

    展开全文
  • 不确定有穷自动机到确定自动机的转换及确定有穷自动机的化简。 1、词法分析程序的功能 词法分析程序(词法分析器、扫描器):执行词法分析的程序,以字符串形式的源程序作为输入,以单词符号或单词符号表示的源程序...
  • 编译原理-确定有穷自动机(DFA)化简(最小化) 预备 最简化DFA:这个DFA没有多余状态、也没有两个相互等价状态。一个DFA可以通过消除无用状态、合并等价状态而转换成一个与之等价最小状态的有穷自动机。 无用...
  • 参考博客地址:https://blog.csdn.net/qq_33605778/article/details/80105658 转载于:https://www.cnblogs.com/xtqjason/p/10251491.html
  • 在编译原理(第三版清华大学出版社出版)中第三章的词法分析中,3.4、3.5、3.6小节中分别讲解了 1、什么是NFA(不确定的有穷自动机)和DFA(确定的有穷自动机) ...5、正规文法和有穷自动机的等价性(根...
  • 编译原理 —— DFA的化简

    万次阅读 多人点赞 2019-05-02 08:50:11
    有穷自动机的多余状态:从自动机的开始状态出发,任何可识别的输入串也不能到达的状态 化简了的DFA M’ 满足两个条件: 没有多余状态 ; 没有两个状态是等价的。 DFA M 的化简方法 求解过程: ① 将DFA M的状态集...
  • 正则语言及其性质

    2020-12-12 19:45:49
    正则语言对应是正则文法,也叫做3型文法。 定义 其中M是有穷自动机,你可以认为是一个DFA,什么是DFA?见文章: DFA确定性有穷自动机及其化简 相关定义:
  • 形式语言与自动机.rar

    2019-08-20 13:33:19
    4.2 正则表达式和有穷自动机的关系 4.3则表达式的等价变换 4.3.1 交换律与结合律 4.3.2 单位元与零元 4.3.3 分配律 4.3.4 与“*”构造有关的定律 4.3.5 发现正则表达式定律的一般方法 4.4 正则表达式的应用 ...
  • 这里"等价"指的是这两个有穷自动机的正规集是相同的。 ε-closure(…)和more(…,…) 在NFA中,ε-closure(A)指的是从状态A经若干ε弧能达到的状态,也包括A自己。more({A,B,C},a)指的是所有从{A,B,C}里的状态经过一...
  • 这里”等价”指的是这两个有穷自动机的正规集是相同的。 ε-closure(…)和more(…,…) 在NFA中,ε-closure(A)指的是从状态A经若干ε弧能达到的状态,也包括A自己。more({A,B,C},a)指的是所有从{A,B,C}里的状态...
  • 4.3.4 确定有穷自动机的化简 4.4 正规式和有穷自动机的等价性 4.5 正规文法和有穷自动机的等价性 4.6 词法分析程序的自动构造工具 4.7 典型例题及解答 练习第5章 自顶向下语法分析方法 5.1 确定的自顶向下分析...
  • 编译原理(第2版)课件

    热门讨论 2009-03-28 15:27:49
    4.3.4 确定有穷自动机的化简 4.4 正规式和有穷自动机的等价性 4.5 正规文法和有穷自动机的等价性 4.6 词法分析程序的自动构造工具 4.7 典型例题及解答 练习第5章 自顶向下语法分析方法 5.1 确定的自顶向下分析思想 ...
  • 编译原理(3):词法分析

    千次阅读 2017-09-18 17:40:25
    本文内容:介绍正则定义,正则表达式,有穷自动机(确定的有穷自动机 DFA,不确定的有穷自动机 NFA), NFA 转换为等价的 DFA,DFA 的化简,识别单词的 DFA ,典型例题及详细解答。
  • 434确定有穷自动机的化简57 44正规式和有穷自动机的等 价性59 45正规文法和有穷自动机间 的转换62 46词法分析程序的自动构造 工具63 461LEX语言64 47练习66 第5章自顶向下语法分析方法69 51确定...
  • 编译原理实验指导书

    2015-12-17 08:37:47
    通过设计、编写和调试将确定的有穷自动机的状态数变为最少的C程序,使得学生掌握化简有穷自动机的过程中的相关概念和方法。DFA的表现形式可以为表格或图形。
  • DFA (Deterministic finite automata, 确定的有穷自动机)是NFA(Nondeterministic finite automata, 非确定的有穷自动机)特例。 对于每个NFA M存在一个DFA M’,使得L(M)=L(M’) 等价性证明 NFA确定化 ...
  • 对于正则表达式,有穷自动机(确定、非确定、带不带ε边)之间的介绍及转化和DFA的化简等知识进行了相关的介绍!
  • 编译原理 词法分析

    2020-11-16 21:39:52
    5、确定有穷自动机(DFA)化简 6、DFA的最小化算法 三、词法分析 1、正规表达式与有限自动机的等价性 2、正规文法与有限自动机的等价性 3、词法分析 一、正规文法和正规式 1、文法与自动机的关系 在这里插入图片描述...

空空如也

空空如也

1 2
收藏数 30
精华内容 12
关键字:

有穷自动机的化简