本文共 9722 字，大约阅读时间需要 32 分钟。

目录

（一）NFA转DFA（2小时）

• 实验目的

学习和掌握将NFA转为DFA的子集构造法。

• 实验任务

（1）存储NFA与DFA；

（2）编程实现子集构造法将NFA转换成DFA。

• 实验内容

(1)确定NFA与DFA的存储格式。要求为3个以上测试NFA准备好相应有限自动机的存储文件。

(2）用C或C++语言编写将NFA转换成DFA的子集构造法的程序。

(3）测试验证程序的正确性。

测试不易。可求出NFA与DFA的语言集合的某个子集（如长度小于某个N），再证实两个语言集合完全相同！（

(4）测试用例参考：将下列语言用RE表示，再转换成NFA使用：

(a) 以a开头和结尾的小字字母串；a (a|b|…|z)*a | a

(b) 不包含三个连续的b的，由字母a与b组成的字符串；(e | b | bb) (a | ab | abb)*

(c) (aa|b)*(a|bb)

1.思路：

• 开始状态S，求出I=ε-closure({S})
• 求出Ia与Ib
• 对未分析过的集合Ia和Ib重复第二步，直到所有的Ia 和Ib都已经被分析过
• 对所有的I、Ia、Ib编号，成为要求的DFA中的状态
• 根据状态转换表构造DFA图中的转换关系

2.数据处理：

字符：

数组 letters[n]（一个下标对应一个字符）

状态：

编号 （一个整数对应一个状态 ）

状态集合：

数表示，表示成二进制的形式 a1,a2,a3……an(2) 其中ai=1表示第i个状态包含在 集合中。

状态之间的转换关系：

二维数组int trans_state[n][n]   ( int S = trans_state[i][j] 表示状态i输入编号为j的字 符后转换到状态S，若S=-1表示输入字符j不进行转换

要处理的计算出的新集合：

set<int> newS存储，这样就不会多次处理相同的集合

char letters[n] ： n个字符Int s ： nfa_s，dfa_s个状态； int nfa_S[nfa_s]，dfa_S[dfa_s]是状态转换图的状态集合int nfa_stateTrans[n][n]：状态转换关系set
   
     dfa_setS： 子集法中计算出的集合，对应DFA中的状态
   

 3.方法：

InputNFA(string path) :: void  从路径path下的文件输入NFANFA2DFA() :: void 将NFA转换为DFAgetIa(int I, int a) :: int 求集合Ia，即在集合I的状态中输入字符a能到达的状态的集合的ε闭包getClosue(int I) :: int 求出集合I的ε闭包

4.NFA2DFA算法的步骤：

①求出初始状态集合的ε闭包，并加入newS

②对newS中的下一个集合I进行处理：计算Ic并加入newS （c是字符集中的字符，j是字符的编号）并且new_StateTrans[i][j] = Ic

③重复2步骤，当处理到newS的最后一个元素时，结束。

④处理new_StateTrans数组，使得dfa_stateTrans[i][j]表示状态i输入字符j后到达的状态编号。（此处需要一个获得状态编号的函数int getStateId(int S)

5.遇到的问题：

• set中元素会自动排序，遍历时会出现问题，因此可以用set来保存一份无重复状态的集合，然后同时存入数组，进行遍历
• 计算Ia时： 注意那些转换状态值为-1的状态，表示在原状态不发出标记该字符的边，不应该作为一个有效状态加入Ia中
• 注意在NFA2DFA中，计算得到的Ia=0时表示为空集合，则写入转换矩阵中相应位置的值是-1，这里的处理是：用getStateId从new_state里面找到状态的索引，如果没找到就返回-1

6.测试： 

2a b41 2 3 41133 2 1-1 1 -1-1 3 4-1 -1 3

 结果：

7.主要代码：

struct FA{    int nfa;//!是否为NFA    int letter_num,snum;//!字符个数,状态个数#    int starts,ends;//!开始状态集合，终止状态集合;    char letters[MAX_LETTER_NUM];//!存储字符#    int state[MAX_STATE_NUM];//!存储状态编号    int stateTrans[MAX_STATE_NUM][MAX_LETTER_NUM];//!状态转换矩阵};

/**将NFA转换为DFA*/FA NFA2DFA(FA nfa){    FA dfa;    std::set 
   
    dfa_setS;//!用来存储新得到的集合,去除重复元素    int new_state[MAX_STATE_NUM];    int I = nfa.starts;    int ends = 0,temp;    int s=1,index=0;//!状态数目和此时处理的集合索引    I = getClosure(nfa,I);//!第一个集合    dfa_setS.insert(I);    new_state[0] = I;    if(I&(nfa.ends)){//!如果该集合包含原NFA的结束状态，则也为DFA的结束状态        ends |= 1<
   

（二）DFA最小化（2小时）

• 实验目的

学会编程实现等价划分法最小化DFA。

• 实验任务

先完善DFA，再最小化DFA。

• 实验内容

（1）准备3个以上测试DFA文件。（提示：其中一定要有没有最小化的DFA）

（2）用C或C++语言编写用等价划分法最小化DFA的程序。

（3）经测试无误。测试不易。可求出两个DFA的语言集合的某个子集（如长度小于某个N），再证实两个语言集合完全相同！

1.思路： 

2.数据处理：

3.方法：

inputDFA(char* path) :: void 从文件输入DFAjudgeIc(int I,vector
   
     PP) :: int 计算集合I中状态属于PP中的不同子集个数getContainerId (int s, vector
    
      PP) :: int 计算状态s包含在PP中的子集的索引getSimplifiedTrans( int S, int c, vector
     
       PP ) :: int 计算状态集合S上输入字符c后到达的状态集合的索引
     
    
   

4.simplifyDFA的思路：

5.测试：

2a b60 1 2 3 4 50 20 1-1 1 2 -1 1 4-1 1 3 -1 3 2-1 0 5-1 5 4

结果：

6.主要代码：

/**DFA最小化算法主体*/FA DFA_simplify(FA dfa){    std::vector 
   
     PP;    //!首先分为终态和非终态两个集合    int temp = (1<<(dfa.snum)) -1;//!状态的全集    PP.push_back(dfa.ends);    PP.push_back(temp - dfa.ends);    int kState[MAX_STATE_NUM];    int I,c,Ic,k,x,mark;//!子集，字符，Ic，Ic属于PP中k个不同子集，mark表示是否删除了子集I    for( int eraseCnt = 0; eraseCnt
    
     1){//!k>1需要划分子集I                for(int j=1; j<=dfa.snum; j++){//!遍历I的每一个状态                    temp = 1<<(dfa.snum -j);                    if(temp&I){//!子集I包含第j个状态                        x = getSimplifiedTrans(dfa,temp,i,PP);//!记录第j个状态在输入c后到达的状态s’属于PP的第x+1 (0~n-1)个子集                        kState[x] |= temp;//!kState中添加第j个状态                    }                }                PP.erase(PP.begin()+eraseCnt);//!擦除PP中的子集I!                mark = 1;//!标记                int cnt = 0;//!计数                int j=0;                while(cnt
    
   

结果检验：

主要代码：

运行结果：

实验心得

• 通过这次实验，我更加注重写代码前的思路整理过程了，在拿到实验题目后，我首先开始回顾相关的知识点，思考方法的封装、数据结构的使用等等，并将思考的过程写在报告里。接下来我便对着之前的思路，进行代码的编写，逐个测试函数的正确性，并在编写代码的过程中记录发现的问题，回过头去思考和修改之前的架构。最后再组装进行案例测试和代码的调试。
• 同时，我也吃了一大亏，一些细节方面的处理，比如状态转换矩阵DFA和NFA的结构没有统一，导致重用函数后发生逻辑错误，最后才回过头来更改相应的数据结构和引用的代码，导致工作量非常的大！
• 另外在实验调试阶段，我通过打印算法执行过程中的关键数据，并结合案例一步一步地分析，对比实际地数据和输出地数据来寻找代码的bug，虽然效率不太高但是也算是对算法流程的又一次熟悉。
• 总之，通过这次试验，我不仅提高了写代码的能力，也巩固了学习到的知识点，收获良多。

源码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define MAX_LETTER_NUM 256#define MAX_STATE_NUM 100#define MAX_STRING_LENGTH 256#define MAX_STRING_NUM 10000/************************数据结构*****************************//*****************************************************************/struct FA{ int nfa;//!是否为NFA int letter_num,snum;//!字符个数,状态个数# int starts,ends;//!开始状态集合，终止状态集合; char letters[MAX_LETTER_NUM];//!存储字符# int state[MAX_STATE_NUM];//!存储状态编号 int stateTrans[MAX_STATE_NUM][MAX_LETTER_NUM];//!状态转换矩阵};/************************公用方法*****************************//*****************************************************************//**!打印转换矩阵*/void printStateTrans(int snum,int num_letter,int stateTrans[MAX_STATE_NUM][MAX_LETTER_NUM]){ printf("Print state transform chart:\n"); int num_s = snum,num_l,j; int i=0; while(num_s>0){ num_l=num_letter;j=0; while(num_l>0){ printf("%d ",stateTrans[i][j++]); num_l--; } printf("\n"); num_s--;i++; } printf("\n\n");}/**计算状态集合I的空闭包E-closure*/int getClosure(FA fa,int I){ int I_new = I;//!新的集合 int num = fa.snum;//!状态个数 int i=0,exist,trans; while(i
         
          0){//!该集合中有第i个状态 trans = fa.stateTrans[i][0];//!输入E后到达的状态trans加入集合I_new if(trans!=-1){ I_new |= (1<<(num-trans-1)); while(fa.stateTrans[trans-1][0] != -1){//!新进来的状态trans输入E后到达的状态也加入I_new trans = fa.stateTrans[trans-1][0]; I_new |= (1<<(num-trans-1)); } } } i++; } return I_new;}/**得到编号为id的状态在字符集合中的索引*/int getStateIndex(int state[MAX_STATE_NUM],int snum,int id){ for(int i=0; i
          
           0){//!该集合中有第i个状态 trans = fa.stateTrans[i][a]; if(trans!=-1)//!输入a后到达的状态trans加入集合Ia Ia |= (1<<(num-trans-1)); } i++; } Ia = getClosure(fa,Ia); return Ia;}/**输入FA的信息，并构造状态转换矩阵*/FA inputFA(char* path){ FILE* fp = fopen(path,"r"); if(fp == NULL){ perror("打开FA文件失败啦"); exit(1); } FA fa;//!建立一个FA结构体对象 int i,num,temp; //!字符输入 fscanf(fp,"%d",&num);//!字符个数 fgetc(fp);//!换行符 fa.letter_num = num; i=0; while(num>0){ fscanf(fp,"%c",&(fa.letters[i++])); fgetc(fp);//!空格 num--; } //!状态输入 fscanf(fp,"%d",&num);//!状态个数 fa.snum = num; i=0; while(num>0){ fscanf(fp,"%d",&(fa.state[i++])); num--; } //!开始状态和结束状态信息 fscanf(fp,"%d",&num);//!开始状态的编号 i= getStateIndex(fa.state,fa.snum,num);//!开始状态在字符集中的位置 fa.starts = 1<<(fa.snum - i -1); fscanf(fp,"%d",&num);//!结束状态个数 fa.ends = 0;i=0; while(num>0){ fscanf(fp,"%d",&temp); i = getStateIndex(fa.state,fa.snum,temp); (fa.ends) |= (1<<(fa.snum-i-1)); num--; } //!转换图的输入(注意最左边一列是输入空字符的列） int num_s = fa.snum,num_l,j; i=0; while(num_s>0){ num_l=fa.letter_num+1;j=0; while(num_l>0){ fscanf(fp,"%d",&num); temp = getStateIndex(fa.state,fa.snum,num); fa.stateTrans[i][j++] = temp; num_l--; } num_s--;i++; } return fa;}/************************NFA转换为DFA*****************************//*****************************************************************//**求集合I在set
           
            dfa_setS中的索引，即编号*/int getStateId(int I, int s, int state[MAX_STATE_NUM]){ for(int i=0;i