编译原理实验二（NFA转DFA、DFA最小化）

（一）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<int> dfa_setS： 子集法中计算出的集合，对应DFA中的状态

 3.方法：

InputNFA(string path) :: void  从路径path下的文件输入NFA
NFA2DFA() :: void 将NFA转换为DFA
getIa(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.测试： 

 

2
a b
4
1 2 3 4
1
1
3
3 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 <int>dfa_setS;//!用来存储新得到的集合,去除重复元素
    int new_state[MAX_STATE_NUM];
    int I = nfa.starts;

    I = getClosure(nfa,I);//!第一个集合
    dfa_setS.insert(I);
    new_state[0] = I;

    //!DFA的状态转换表的构造
    int s=1,index=0;//!状态数目和此时处理的集合索引
    int ends = 0;
    while(index<s){
        I = new_state[index];
        for(int i=0; i<nfa.letter_num; i++){//!对每一个字符a求出Ia
            int Ia = getIa(nfa,I,i+1);
            if( Ia!=0 && dfa_setS.find(Ia)==dfa_setS.end()){//!若新生成的集合没有被生成过，则加入遍历集合
                new_state[s++] = Ia;
                dfa_setS.insert(Ia);//!得到的新的集合加入set集合
            }
            dfa.stateTrans[index][i] = getStateId(Ia,s,new_state);//!设置dfa中在状态s输入字符a后到达的状态
            dfa.state[i] = i+1;//!给DFA的状态编号
            if(Ia&(nfa.ends))//!如果该集合包含原NFA的结束状态，则也为DFA的结束状态
                ends |= 1<<s;
        }
        index++;
    }
    dfa.snum = s;//!DFA的状态数目
    dfa.starts = 1;//!NFA的开始状态
    dfa.ends = 0;
    //!处理结束状态集合
    for(int i=0;i<dfa.snum;i++){
        if(ends&(1<<i)){//第i+1个状态是结束状态
            (dfa.ends) |= (1<<(dfa.snum-i-1));
        }
    }

    //!dfa的其他数据处理
    dfa.nfa = 0;
    dfa.letter_num = nfa.letter_num;
    for(int i = 0; i< nfa.letter_num; i++){
        dfa.letters[i] = nfa.letters[i];
    }

    return dfa;
}

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

• 实验目的

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

• 实验任务

先完善DFA，再最小化DFA。

• 实验内容

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

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

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

1.思路： 

 

2.数据处理：

3.方法：

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

4.simplifyDFA的思路：

5.测试：

2
a b
6
0 1 2 3 4 5
0 
2
0 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 <int> 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<PP.size();){//!遍历保存子集的集合PP
        mark =0;
        I = *(PP.begin()+eraseCnt);//!一个子集
        for(int i=1; i<=dfa.letter_num; i++){//!遍历字符集letters
            //!c为第i个字符
            Ic = getIa(dfa, I, i);//!得到Ic
            k = judgeIc(Ic,dfa.snum,PP);//!Ic属于PP中k个不同子集
            memset(kState,0,sizeof(int)*MAX_STATE_NUM);//!初始化kState为全0
            if(k>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<k){
                    temp = kState[j++];
                    if(temp){//!Ic的一子集temp,包含于PP中第j+1个子集
                        PP.push_back(temp);cnt++;
                    }
                }
                break;//!找到一个可以划分I的字符c后就处理下一个子集I
            }
        }
        if(!mark){
                eraseCnt++;//!删除了子集I后it自然后移一位不需要++
        }
    }

    FA dfa_new;
    dfa_new.snum = PP.size();
    dfa_new.nfa = 0;
    dfa_new.letter_num = dfa.letter_num;
    strcpy(dfa_new.letters,dfa.letters);
    dfa_new.starts = dfa_new.ends = 0;
    for( int i = 0; i<PP.size();i++){//!开始和终止状态的处理
        int I = *(PP.begin()+i);
        if(I&dfa.starts){
            dfa_new.starts |=(1<<(dfa_new.snum-i-1));
        }
        if(I&dfa.ends){
            dfa_new.ends |=(1<<(dfa_new.snum-i-1));
        }

    }

    //!状态转换矩阵的处理
       for( int i = 0; i<PP.size();i++){//!开始和终止状态的处理
        int I = *(PP.begin()+i);
        dfa_new.stateTrans[i][0]= -1;//!空字符的处理为无效-1
        for( int j=1; j<=dfa_new.letter_num; j++){//!字符集合中字符j
            dfa_new.stateTrans[i][j]=getSimplifiedTrans(dfa,I,j,PP);
        }
    }

    return dfa_new;
}

 

源码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <set>
#include <vector>

#define MAX_LETTER_NUM 256
#define MAX_STATE_NUM 100

/************************数据结构*****************************/
/*****************************************************************/

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<num){
        exist = 1<<(num - i-1);
        if( (exist&I)>0){//!该集合中有第i个状态
            trans = fa.stateTrans[i][0];//!输入E后到达的状态trans加入集合I_new
            if(trans!=-1){
                I_new |= (1<<(num-trans));
                while(fa.stateTrans[trans-1][0] != -1){//!新进来的状态trans输入E后到达的状态也加入I_new
                    trans = fa.stateTrans[trans-1][0];
                    I_new |= (1<<(num-trans));
                }
            }
        }
        i++;
    }
    return I_new;
}

/**得到编号为id的状态在字符集合中的索引*/
int getStateIndex(int state[MAX_STATE_NUM],int snum,int id){
    for(int i=0; i<snum; i++)
        if(state[i] == id)
            return i;
    return -1;
}

/**求状态集合I输入字符a后到达的集合的E-closure*/
int getIa(FA fa,int I, int a){
    int Ia = 0;
    int num = fa.snum;//!状态个数
    int i=0,exist,trans;
    while(i<num){
        exist = 1<<(num - i-1);
        if( (exist&I)>0){//!该集合中有第i个状态
            trans = fa.stateTrans[i][a];
            if(trans!=-1)//!输入a后到达的状态trans加入集合Ia
                Ia |= (1<<(num-trans));
        }
        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);
            if(temp!= -1) temp++;
            fa.stateTrans[i][j++] = temp;
            num_l--;
        }
         num_s--;i++;
    }
    return fa;
}

/************************NFA转换为DFA*****************************/
/*****************************************************************/

/**求集合I在set<int>dfa_setS中的索引，即编号*/
int getStateId(int I, int s, int state[MAX_STATE_NUM]){
    for(int i=0;i<s; i++){
        if(state[i] == I)
            return i;
    }
    return -1;
}

/**将NFA转换为DFA*/
FA NFA2DFA(FA nfa){
    FA dfa;
    std::set <int>dfa_setS;//!用来存储新得到的集合,去除重复元素
    int new_state[MAX_STATE_NUM];
    int I = nfa.starts;

    I = getClosure(nfa,I);//!第一个集合
    dfa_setS.insert(I);
    new_state[0] = I;

    //!DFA的状态转换表的构造
    int s=1,index=0;//!状态数目和此时处理的集合索引
    int ends = 0;
    while(index<s){
        I = new_state[index];
        for(int i=0; i<nfa.letter_num; i++){//!对每一个字符a求出Ia
            int Ia = getIa(nfa,I,i+1);
            if( Ia!=0 && dfa_setS.find(Ia)==dfa_setS.end()){//!若新生成的集合没有被生成过，则加入遍历集合
                new_state[s++] = Ia;
                dfa_setS.insert(Ia);//!得到的新的集合加入set集合
            }
            dfa.stateTrans[index][i] = getStateId(Ia,s,new_state);//!设置dfa中在状态s输入字符a后到达的状态
            dfa.state[i] = i+1;//!给DFA的状态编号
            if(Ia&(nfa.ends))//!如果该集合包含原NFA的结束状态，则也为DFA的结束状态
                ends |= 1<<s;
        }
        index++;
    }
    dfa.snum = s;//!DFA的状态数目
    dfa.starts = 1;//!NFA的开始状态
    dfa.ends = 0;
    //!处理结束状态集合
    for(int i=0;i<dfa.snum;i++){
        if(ends&(1<<i)){//第i+1个状态是结束状态
            (dfa.ends) |= (1<<(dfa.snum-i-1));
        }
    }

    //!dfa的其他数据处理
    dfa.nfa = 0;
    dfa.letter_num = nfa.letter_num;
    for(int i = 0; i< nfa.letter_num; i++){
        dfa.letters[i] = nfa.letters[i];
    }

    return dfa;
}


/************************DFA最小化********************************/
/*****************************************************************/


/**计算集合I中状态属于PP中的不同子集个数*/
int judgeIc(int I,int snum,std::vector<int> PP){
    int cnt = 0,states;
    for(std::vector<int>::iterator it = PP.begin(); it!=PP.end(); it++){
        states = *it;
        if(I&states)
            cnt++;
    }
    return cnt;
}

/**计算状态s包含在PP中的子集的索引*/
int getContainerId (int s, std::vector<int> PP){
   int index = 0,states;
    for(std::vector<int>::iterator it = PP.begin(); it!=PP.end(); it++){
        states = *it;
        if(s&states)
            return index;
        index++;
    }
    return -1;
}

/**计算状态集合S上输入字符c后到达的PP中子集的索引*/
int getSimplifiedTrans(FA dfa,int S, int c, std::vector<int> PP ){
    int index = 0,trans,temp;
    int snum = dfa.snum;
    for(int i=1; i<=snum; i++){
        temp = 1<<(snum-i);//!第i个状态
        if(S&temp){//!状态集合S中包含第i个状态
            trans = dfa.stateTrans[i-1][c];
            if(trans!=-1){//!第i个状态输入字符c后达到状态trans
                trans = 1<<(snum-trans);//!状态编号转换为状态集合形式
                return getContainerId(trans,PP);
            }
        }
    }
    return -1;
}

/**DFA最小化算法主体*/
FA DFA_simplify(FA dfa){
    std::vector <int> 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<PP.size();){//!遍历保存子集的集合PP
        mark =0;
        I = *(PP.begin()+eraseCnt);//!一个子集
        for(int i=1; i<=dfa.letter_num; i++){//!遍历字符集letters
            //!c为第i个字符
            Ic = getIa(dfa, I, i);//!得到Ic
            k = judgeIc(Ic,dfa.snum,PP);//!Ic属于PP中k个不同子集
            memset(kState,0,sizeof(int)*MAX_STATE_NUM);//!初始化kState为全0
            if(k>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<k){
                    temp = kState[j++];
                    if(temp){//!Ic的一子集temp,包含于PP中第j+1个子集
                        PP.push_back(temp);cnt++;
                    }
                }
                break;//!找到一个可以划分I的字符c后就处理下一个子集I
            }
        }
        if(!mark){
                eraseCnt++;//!删除了子集I后it自然后移一位不需要++
        }
    }

    FA dfa_new;
    dfa_new.snum = PP.size();
    dfa_new.nfa = 0;
    dfa_new.letter_num = dfa.letter_num;
    strcpy(dfa_new.letters,dfa.letters);
    dfa_new.starts = dfa_new.ends = 0;
    for( int i = 0; i<PP.size();i++){//!开始和终止状态的处理
        int I = *(PP.begin()+i);
        if(I&dfa.starts){
            dfa_new.starts |=(1<<(dfa_new.snum-i-1));
        }
        if(I&dfa.ends){
            dfa_new.ends |=(1<<(dfa_new.snum-i-1));
        }

    }

    //!状态转换矩阵的处理
       for( int i = 0; i<PP.size();i++){//!开始和终止状态的处理
        int I = *(PP.begin()+i);
        dfa_new.stateTrans[i][0]= -1;//!空字符的处理为无效-1
        for( int j=1; j<=dfa_new.letter_num; j++){//!字符集合中字符j
            dfa_new.stateTrans[i][j]=getSimplifiedTrans(dfa,I,j,PP);
        }
    }

    return dfa_new;
}



int main(){
    char Path[125];//!输入文件的路径
    strcpy(Path,"NFA.txt");
    /********NFA转DFA*********/
    printf("NFA TO DFA:\n");
    FA nfa = inputFA(Path);
    nfa.nfa =1;
    printStateTrans(nfa.snum,nfa.letter_num+1,nfa.stateTrans);
    FA dfa1 = NFA2DFA(nfa);
    printStateTrans(dfa1.snum,dfa1.letter_num,dfa1.stateTrans);

    /********NFA转DFA*********/
    printf("MININUM DFA:\n");
    strcpy(Path,"DFA1.txt");
    FA dfa2 = inputFA(Path);
    dfa2.nfa = 0;
    printStateTrans(dfa2.snum,dfa2.letter_num+1,dfa2.stateTrans);
    FA dfa2_new = DFA_simplify(dfa2);
    printStateTrans(dfa2_new.snum,dfa2_new.letter_num+1,dfa2_new.stateTrans);
    return 0;
}