精华内容
下载资源
问答
  • DFA确定化和最小化

    2021-03-23 15:56:15
    二、再将NFA转成DFA(子集法) 运用子集法的3个概念: (1 )状态集的ε-闭包: 状态集I中的任何状态s经任意条ε弧而能到达的所有状态的集合,定义为状态集I的ε -闭包,表示为ε−closure()ε -closure()ε−closure()...

    从正规式开始

    一、先将正规式转换成NFA

    通过下面的对应法则将正规式转换成NFA

    img

    例如:

    img

    二、再将NFA转成DFA(子集法)

    运用子集法的3个概念:
    (1 )状态集的ε-闭包: 状态集I中的任何状态s经任意条ε弧而能到达的所有状态的集合,定义为状态集I的ε -闭包,表示为εclosure()ε -closure()

    (2)状态集的a弧转换: 状态集I中的任何状态s经过一条a弧而能到达的所有状态的集合,定义为状态集1的a弧转换,表示为move(l,a)。

    (3)状态集的a弧转换的闭包a:lg=εclosure(move(l,a))lg= ε-closure(move(l,a))

    上面的正规式转换成NFA:

    img

    先从初态0开始求:

    【因为每个状态通过一条ε弧到达自己本身,所以求得ε的闭包包含自己】

    (1)求0的ε的闭包:经过任意条ε所能到达的状态,集合为{0,1,3,4,5,6,7,9}

    (2)求0的a弧转换:1经过a弧到达2,4经过a弧到达4,其余没有经过一条a弧到达某个状态,所以集合为{2,4}
    (3)求a弧转换的闭包:{2,4}分别经过任意条ε所能到达的状态,集合为{2,4,6,7,9}

    (4)求0的b弧转换:5经过b到5,7经过b到8,,其余没有经过一条b弧到达某个状态,所以集合为{5,8}

    (5)求b弧转换的闭包:{5,8}分别经过任意条ε所能到达的状态,集合为{5,6,7,8,9}
    0的ε-闭包:{0,1,3,4,5,6,7,9}
    0的a弧转换:{2,4}
    0的a弧转换的ε-闭包:{2,4,6,7,9}
    0的b弧转换:{5,8}
    0的b弧转换的ε-闭包:{5,6,7,8,9}
    现在列一个表格:
    (1)表格的列数为输入字符的个数+1,此题为a,b两个输入字符,所以为3列。
    (2)第一列第一行填写初态的ε-闭包(此题0的ε-闭包),第二列第一行填写初态的a弧转换的ε-闭包(此题0的a弧转换的ε-闭包),第三列第一行填写初态的b弧转换的ε-闭包(此题0的b弧转换的ε-闭包)…以此类推。
    (3)第一列的第二行以下填入上一行第二列以后的没有出现过的状态集。(此题第一行第二列第三列都没有出现在第一列中,将他们填入第一列)

    I IaI_a IbI_b
    {0,1,3,4,5,6,7,9} {2,4,6,7,9} {5,6,7,8,9}
    {2,4,6,7,9}
    {5,6,7,8,9}

    下图为填好的表:
    【新的终态的判断方法就是包含原来终态的集合就为终态,例如此题原来终态为9,所以包含9的集合就为终态,[双圈代表终态];
    新的初态就是包含原来初态的集合就为初态,例如此题原来初态为0,所以包含0的集合就为初态】

    img

    为表里的状态集重新标上号:

    img

    可以得到下面的图:

    img

    这个图是还不是最小化的DFA,还需要DFA最小化。但下面DFA最小化重新举例。

    三、将DFA最小化

    先了解几个概念:

    1.多余状态:对于一个状态SiS_i,若从开始状态出发,不可能到达改状态Si,则Si为多余(无用)状态。

    2.死状态:对于一个状态Si,对于任意输入符号a,若转到它本身后,不可能从它到达终止状态,则称Si为死状态。

    1,2都称为无关状态

    3.等价状态:若Si为自动机的一个状态,我们把从Si出发能导出的所有符号串的集合记为L(Si)。
    设有两个状态Si和Sj,若有LSi=LSjL(Si)=L(Sj),则称Si和Sj是等价状态。

    4.可区别状态:自动机中两个状态Si和Sj,如果它们不等价,则称它们可区别。

    5.两个状态(Si和Sj)等价的判断条件:

    (1)状态Si和Sj必须同时为终止状态或同时为非终止状态。即终止状态和非终止状态是可区别的。

    (2)状态Si和Sj对于任意输入符a∈Σ,必须转到等价的状态里,否则Si和Sj是可区别的。

    DFA的化简算法:对于DFA M=(S,Σ,f,S0,Z)
    (1)首先将DFA的状态集进行初始化,分成Π=(Z,S-Z);
    (2) 用下面的过程对Π构造新的划分Π new
    for (Π中每个组G) do //每个组都是一个状态集
    begin
    把G划分成小组,G中的任意两个状态Si和Sj在同一组中,当且仅当对于Σ中任意输入符号a ,Si和Sj的a转换是到同一组中,move(Si,a) ∈Gi ,move(Sj,a) ∈Gi。这样,只要Si和Sj的a转换是到不同的组中,则说明Si和Sj是可区别的,可进行划分。在Π new中用刚完成的对G的划分代替原来的G。
    end ; Π := Π new;
    (3)重复执行(2),直到Π中每个状态集不能再划分(Π new= Π)为止;
    (4)合并等价状态 ,在每个G中,取任意状态作为代表,删去其它状态;
    (5)删去无关状态,从其它状态到无关状态的转换都成为无定义。
    举例:

    img

    ①首次划分: Π0=({2,3,4,5},{0,1})

    ②在G={2,3,4,5}中:f(2,a)=1,f(4,a)=0(转向终态集{0,1});f(3,a)=3,f(5,a)=5(转向非终态集{2,3,4,5}),故{2,4}和{3,5}是可区别的,得Π1=({2,4},{3,5},{0,1});

    ③在G={2,4}中,f(2,a)=1,f(4,a)=0(转向终态子集),而f(2,b)=3,f(4,b)=5(转向非终态子集{3,5}),所以不可区别,不再进行划分;

    ④考察G={3,5},f(3,a)=3,f(5,a)=5(转向非终态子集{3,5}),f(3,b)=2,f(5,b)=4(转向非终态子集{2,4}), 所以不可区别,不再进行划分;

    ⑤考察G={0,1},f(0,a)=f(1,a)=1(转向终态集{0,1}); f(0,b)=2,f(1,b)=4(转向非终态子集{2,4}),所以不可区别,不再进行划分;

    ⑦进一步进行考察,可以发现每个子集都不能再划分了;

    ⑧消去等价状态:{0,1}用0表示,{2,4}用2表示,{3,5}用3表示,如右图所示

    ⑨去掉无关状态,因DFA M’中没有无关状态,所以下图即为最后结果。

    img

    展开全文
  • DFA确定化和最小化 从正规式开始 一、先将正规式转换成NFA 通过下面的对应法则将正规式转换成NFA 例如: 二、再将NFA转成DFA(子集法) 运用子集法的3个概念: (1 )状态集的ε-闭包: 状态集I中的任何状态s经...

    【编译原理】NFA到DFA转换的实例&&DFA确定化和最小化

    在这里插入图片描述

    从正规式开始

    一、先将正规式转换成NFA

    通过下面的对应法则将正规式转换成NFA


    在这里插入图片描述

    例如:


    在这里插入图片描述

    二、再将NFA转成DFA(子集法)

    运用子集法的3个概念:
    (1 )状态集的ε-闭包: 状态集I中的任何状态s经任意条ε弧而能到达的所有状态的集合,定义为状态集I的ε -闭包,表示为ε -closure()。

    (2)状态集的a弧转换: 状态集I中的任何状态s经过一条a弧而能到达的所有状态的集合,定义为状态集1的a弧转换,表示为move(l,a)。

    (3)状态集的a弧转换的闭包a: lg= ε-closure(move(l,a))

    上面的正规式转换成NFA:


    在这里插入图片描述

    先从初态0开始求:
      【因为每个状态通过一条ε弧到达自己本身,所以求得ε的闭包包含自己】
    (1)求0的ε的闭包:经过任意条ε所能到达的状态,集合为{0,1,3,4,5,6,7,9}
    (2)求0的a弧转换:1经过a弧到达2,4经过a弧到达4,其余没有经过一条a弧到达某个状态,所以集合为{2,4}
    (3)求a弧转换的闭包:{2,4}分别经过任意条ε所能到达的状态,集合为{2,4,6,7,9}
    (4)求0的b弧转换:5经过b到5,7经过b到8,,其余没有经过一条b弧到达某个状态,所以集合为{5,8}
    (5)求b弧转换的闭包:{5,8}分别经过任意条ε所能到达的状态,集合为{5,6,7,8,9}
    0的ε-闭包:{0,1,3,4,5,6,7,9}
    0的a弧转换:{2,4}
    0的a弧转换的ε-闭包:{2,4,6,7,9}
    0的b弧转换:{5,8}
    0的b弧转换的ε-闭包:{5,6,7,8,9}
    现在列一个表格:
    (1)表格的列数为输入字符的个数+1,此题为a,b两个输入字符,所以为3列。
    (2)第一列第一行填写初态的ε-闭包(此题0的ε-闭包),第二列第一行填写初态的a弧转换的ε-闭包(此题0的a弧转换的ε-闭包),第三列第一行填写初态的b弧转换的ε-闭包(此题0的b弧转换的ε-闭包)......以此类推。
    (3)第一列的第二行以下填入上一行第二列以后的没有出现过的状态集。(此题第一行第二列第三列都没有出现在第一列中,将他们填入第一列)

    I Ia Ib
    {0,1,3,4,5,6,7,9} {2,4,6,7,9} {5,6,7,8,9}
    {2,4,6,7,9}
    {5,6,7,8,9}

    下图为填好的表:
    【新的终态的判断方法就是包含原来终态的集合就为终态,例如此题原来终态为9,所以包含9的集合就为终态,[双圈代表终态];
    新的初态就是包含原来初态的集合就为初态,例如此题原来初态为0,所以包含0的集合就为初态】


    在这里插入图片描述


    为表里的状态集重新标上号:


    在这里插入图片描述


    可以得到下面的图:

    在这里插入图片描述


    这个图是还不是最小化的DFA,还需要DFA最小化。但下面DFA最小化重新举例。
    三、将DFA最小化

    先了解几个概念:
    1.多于状态:对于一个状态Si,若从开始状态出发,不可能到达改状态Si,则Si为多余(无用)状态。
    2.死状态:对于一个状态Si,对于任意输入符号a,若转到它本身后,不可能从它到达终止状态,则称Si为死状态。
    都称为无关状态
    3.等价状态:若Si为自动机的一个状态,我们把从Si出发能导出的所有符号串的集合记为L(Si)。
    设有两个状态Si和Sj,若有L(Si)=L(Sj),则称Si和Sj是等价状态。
    4.可区别状态:自动机中两个状态Si和Sj,如果它们不等价,则称它们可区别。
    5.两个状态(Si和Sj)等价的判断条件:
    (1)状态Si和Sj必须同时为终止状态或同时为非终止状态。即终止状态和非终止状态是可区别的。
    (2)状态Si和Sj对于任意输入符a∈Σ,必须转到等价的状态里,否则Si和Sj是可区别的。

    DFA的化简算法:对于DFA M=(S,Σ,f,S0,Z)
    (1)首先将DFA的状态集进行初始化,分成Π=(Z,S-Z);
    (2) 用下面的过程对Π构造新的划分Π new
    for (Π中每个组G) do //每个组都是一个状态集
    begin
    把G划分成小组,G中的任意两个状态Si和Sj在同一组中,当且仅当对于Σ中任意输入符号a ,Si和Sj的a转换是到同一组中,move(Si,a) ∈Gi ,move(Sj,a) ∈Gi。这样,只要Si和Sj的a转换是到不同的组中,则说明Si和Sj是可区别的,可进行划分。在Π new中用刚完成的对G的划分代替原来的G。
    end ; Π := Π new;
    (3)重复执行(2),直到Π中每个状态集不能再划分(Π new= Π)为止;
    (4)合并等价状态 ,在每个G中,取任意状态作为代表,删去其它状态;
    (5)删去无关状态,从其它状态到无关状态的转换都成为无定义。
    举例:

    在这里插入图片描述


    ①首次划分: Π0=({2,3,4,5},{0,1})
    ②在G={2,3,4,5}中:f(2,a)=1,f(4,a)=0(转向终态集{0,1});f(3,a)=3,f(5,a)=5(转向非终态集{2,3,4,5}),故{2,4}和{3,5}是可区别的,得Π1=({2,4},{3,5},{0,1});
    ③在G={2,4}中,f(2,a)=1,f(4,a)=0(转向终态子集),而f(2,b)=3,f(4,b)=5(转向非终态子集{3,5}),所以不可区别,不再进行划分;
    ④考察G={3,5},f(3,a)=3,f(5,a)=5(转向非终态子集{3,5}),f(3,b)=2,f(5,b)=4(转向非终态子集{2,4}), 所以不可区别,不再进行划分;
    ⑤考察G={0,1},f(0,a)=f(1,a)=1(转向终态集{0,1}); f(0,b)=2,f(1,b)=4(转向非终态子集{2,4}),所以不可区别,不再进行划分;
    ⑦进一步进行考察,可以发现每个子集都不能再划分了;
    ⑧消去等价状态:{0,1}用0表示,{2,4}用2表示,{3,5}用3表示,如右图所示
    ⑨去掉无关状态,因DFA M’中没有无关状态,所以下图即为最后结果。

    在这里插入图片描述

    image.png

    之前上面这个图画错了,现在图已经修改过了,谢谢提醒 :-D

    展开全文
  • 编译原理中的NFA确定化和DFA最小化可运行代码以及思路解释
  • 编译原理——NFA确定化和DFA最小化

    万次阅读 2018-04-05 14:12:54
    先完善DFA,再最小化DFA。 二、实验内容 确定NFA与DFA的存储格式。要求为3个以上测试NFA准备好相应有限自动机的存储文件。 用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。 准备3个以上测试DF...

    前言:这是我学习编译原理,课程实验的内容,课程早已结束,现整理发表。

    一、实验任务

    1. 存储NFA与DFA;
    2. 编程实现子集构造法将NFA转换成DFA。
    3. 先完善DFA,再最小化DFA。

    二、实验内容

    1. 确定NFA与DFA的存储格式。要求为3个以上测试NFA准备好相应有限自动机的存储文件。
    2. 用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。
    3. 准备3个以上测试DFA文件。(提示:其中一定要有没有最小化的DFA)
    4. DFA手动完善。(状态转换映射要是满映射)
    5. 用C或JAVA语言编写用等价划分法最小化DFA的程序。

    其实这部分内容要求没这么简单的,还有验证是否转换成功,怎么验证呢?只要你求出原来的和改后的某个子集(如长度小于某个N),再证实两个语言集合完全相同。不过当初我忘了这个了,后来验收的时候才发现没写,所以这部分我也不会加进来了。 ̄ω ̄=


    三、存储格式

    dfa

    3 // 字符集中的字符个数 (以下两行也可合并成一行)
    / * o // 以空格分隔的字符集。O代表任意非/和*的字符
    5 // 状态个数 (以下两行也可合并成一行)
    1 2 3 4 5 // 状态编号。若约定总是用从1开始的连续数字表示,则此行可省略
    1 // 开始状态的编号。若约定为1,则此行可省
    1 // 结束状态个数。若约定为1,则此行可省略
    5 // 结束状态的编号
    2  -1  -1 // 状态1的所有出去的转换。按字符集中的字符顺序给出。-1表示出错状态
    -1  3  -1
    -1  4   3
    5   4   3
    -1  -1  -1
    

    这部分不会照搬的,到后面输入会修改。不过大致还是这样的格式。


    四、程序设计

    • 实现思路

    想想还是写一点点吧,否则感觉缺点什么。

    nfa和dfa来看的大致都知道了,转换的话只要是用子集构造法。至于子集构造法怎么样的,大家自己查吧,我要说的就是注意空字符的到达处理,循环需要注意。
    而dfa最小化是最简单的吧,我反正就是先分为先分为是接受状态的集合和不是接受状态的集合,然后把转换状态相同的分为一个状态就可以了。当然,要修改状态的转换。

    • 文件说明:

        1. intArr.h intArr.cpp 数组类,用于实现数字集合的并,删除,查找
        2. NFA_To_DFA.h NFA_To_DFA.cpp dfa转nfa的类
        3. minimalDFA.h minimalDFA.cpp 最小化dfa的类
        4. main.cpp 主函数
      
    • 类设计说明

    1)intArr类

    class intarr
    {
    public:
        intarr();
        intarr(intarr &arr1);                   //复制构造函数
        int inline getSize(){return size;}      //获取集合大小
        void cleanArr();                        //清空集合元素
        void operator &= (int num);             //重载&=,并入单个元素
        void operator &= (intarr &arr1);        //重载&=,并入一个集合
        void getSort();                         //对集合元素从小到大排序
        int &operator[](int i);                 //重载[],可以向数组一样获得元素
        bool operator == (intarr &arr1);        //重载==,判断两个集合是否相等
        bool getNum(int num);                   //判断一个数字是否在集合中
        void delNum(int num);                   //删除一个数字
        int getNumber();                        //获得创建对象的个数
    
    private:
        int *arr=NULL;      //数组指针
        int size;           //数组大小
        static int number;  //创建对象的个数
    };
    
    

    2) NFA_To_DFA类

    dfa中的dfa集合

    struct state
    {
        int stateNum;        //这个状态的编号
        int *nextNum;        //根据输入字符将会指向哪些状态
        intarr nfaArr;       //NFA状态集
        bool isMake = false; //是否标记
        static int maxNum;   //最大状态标号
    };
    
    

    共享的一个dfa状态,作为一个中间状态用于创建新的dfa状态

    struct sstate
    {
        intarr nfaArr; //NFA状态集
        int stateNum = 0;
    };
    
    

    nfa转dfa的类

    class nfa_to_dfa
    {
      public:
        nfa_to_dfa(std::string fn); //默认构造函数
        void getIntArr(int num, std::string s);
        void closure_s();                     //空字符匹配
        void closure_T(int num, int charNum); //字符集匹配
        void inStates();                      //是否在当前DFA状态中了
        void read();                          //读取NFA数据
        void convert();                       //开始转换
        void output();
        ~nfa_to_dfa() {} //析构函数
    
      private:
        std::string charracters;          //nfa字符集
        int charrLength = 0;              //字符集的长度
        int statesNumber = 0;             //nfa状态个数,默认为0
        int currState = 1;                //开始状态编号,默认为1,不用输入
        int endNum = 1;                   //nfa接受状态个数,默认为1
        int *acceptStates = NULL;         //nfa接受状态集
        std::string **convertFrom = NULL; //转换表
        std::string filePath;             //文件输入对象
        sstate shareState;                //一个共享对象,用于转换
    
        int acceptNum = 0;      //转换出的dfa接受状态个数
        intarr DfaAcceptstates; //dfa接受状态集
    };
    
    

    3)minimalDFA类

    最小化dfa的一个状态,用结构体描述

    struct minState
    {
        static int maxNum;      //最大状态数
        intarr sameState;       //相同的输出的状态集合
        int  minNum;            //这个最小dfa的状态标
        int *nextState=NULL;    //不同输入字符的情况下指向不同状态的集合
        int isAcceptState=0;    //是否为接受状态
    };
    
    

    最小化dfa。算法思想:
    先将状态划分为接受状态和非接受状态。对于dfa中在输入相同的字符转到相同的状态的状态把这些状态划分到一组。

    class minDfa
    {
      public:
        minDfa(std::string str);  //构造函数
        void read();              //读取数据
        void divide();            //划分dfa
        void output();            //状态集
        bool isqueal();           //判断两个最小化dfa是否相等
    
      private:
        std::string charracters;  //字符集
        int charLength=0;
        int stateNum = 0;         //状态个数,默认为0
        int currState = 1;        //开始状态编号,默认为1
        int endNum = 1;           //接受状态个数,默认为1
        int *acceptState = NULL;  //接受状态
        int **convertFrom = NULL; //转换表
        minState *states;         //最小化dfa状态集
        std::string path;         //要读取文件的路劲
    };
    
    

    五、实验测试

    • 输入的nfa文件中

       第一行 为字符集 ,?表示空字符
       第二行 为状态个数,默认为从状态1开始,所以不用输入开始状态 
       第三行 为行为接受状态个数 
       第四行 为接受状态 
       第五行 开始为状态转换表。列为字符集,对应为一个二维数组,在哪个状态输入哪个字符转到哪个状态,-1为错误状态。
      
    • NFA转换为DFA

    1)nfa_to_dfa的输入文件nd:(aa|b)*(a|bb)*

    ab?
    4
    1
    3
    2,1,3,
    1,-1,-1,
    3,4,-1,
    -1,3,-1,
    
    

    2)在文件dfa_to_nfa中输出:

    ab
    5
    4
    1 2 3 5 
    {1,3,}		2 3 
    {2,3,}		1 4 
    {1,3,4,}		2 3 
    {4,}		-1 5 
    {3,}		5 4 
    
    

    3)作为minDfa的输入文件dfa:

    ab
    5
    4
    1 2 3 5 
    2 3 
    1 4 
    2 3 
    -1 5 
    5 4 
    
    

    4)最小化mindfa输出

    {1,3,}	1: 2 1 		isacceptstate:1
    {2,}	2: 1 3 		isacceptstate:1
    {4,}	3: -1 4 		isacceptstate:0
    {5,}	4: 4 3 		isacceptstate:1
    ***********
    

    六、实验总结

    来看怎么写的肯定要失望了,因为除了贴了些类的说明,也没有什么好参考的。我也知道我该写下是怎么写nfa转dfa,dfa怎么转换的,代码该怎么写,但是,太久了,我忘记了,你们可以直接看代码理解。还有如果对比是不是觉得我分文件啊,用结构体啊,用类啊写的好复杂啊,其实我也觉得挺复杂的,但是事实上大规模的代码实现分文件写是很好的,方便修改,如果一个文件维护修改会很麻烦,当初我也是第一次写这么多的分文件代码。但总的收获是不少的,中间遇到了许多问题,可以的话,试下这样写吧。


    七、资料下载

    具体代码见NFA_TO_NFA

    展开全文
  • 文章目录实验二 NFA确定化和DFA最小化(4学时)(一)NFA转DFA(2小时)一、实验目的二、实验任务三、实验内容(二)DFA最小化(2小时)一、实验目的二、实验任务三、实验内容**四、通用NFA存储格式的建议(用以上的...

    代码链接:编译原理实验二

    实验二 NFA确定化和DFA最小化(4学时)

    (一)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)*

      © ( a a | b ) * ( a | b b )*

    (二)DFA最小化(2小时)

    一、实验目的

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

    二、实验任务

    先完善DFA,再最小化DFA。

    三、实验内容

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

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

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

    四、通用NFA存储格式的建议(用以上的第三个测试NFA为例)

    在这里插入图片描述

    2 // 字符集中的字符个数 (以下两行也可合并成一行)
    a b // 以空格分隔的字符集。
    4 // 状态个数 (以下两行也可合并成一行)
    1 2 3 4 // 状态编号。若约定总是用从1开始的连续数字表示,则此行可省略
    1 // 开始状态的编号。若约定为1,则此行可省略
    1 // 结束状态个数。若约定为1,则此行可省略
    3 // 结束状态的编号
    3 2 1 // 状态1的所有出去的转换。按字符集中的字符顺序给出,并在最左边加上一列关于e的转换。-1表示出错状态。若下一个状态有多个时,多个状态用逗号分隔。
    -1 1 -1
    -1 3 4
    -1 -1 3
    

    五、集合状态的内部表示的建议

    使用示性函数。也即:

    1. 含有单个状态的状态集合用2的幂次表示。即状态1 ~ N分别用数21 ~ 2N 表示。

    2. 数的存储:若用32位整型(__int32)、64位整型(__int64)存储,可分别表示32个或64个状态。更多的状态表示需要使用整型数组。

    3. 含有多个状态的状态集合也用数来表示。若两个状态集合A与B用数表示为m和n,则状态集合AÈB与AÇB的数可用“位运算”表示,分别为m|n和m&n。

    4. 若想知道某个状态集合A(用数m表示)中是否包含原先的第i个状态,也可使用基于“位运算”来判断:若(m | 2i )> 0,则包含,否则不包含。

    实验通过测试后,按规定时间上交源代码、测试样例、输出文件(如有输出文件)和电子版实验报告。

    实验步骤

    确定NFA和DFA的存储格式

    NFA格式:

    2       // 输入的字符集的个数
    ab       // 字符集 中间无空格
    14       // NFA状态总数n:编号从0开始到n-1,默认起始状态为0
    1       // 终结状态个数
    13       // 终结状态编号
    1,7 -1 -1   // 以下n行输入当前状态的转换
    2,4 -1 -1   // 无转换用-1代替
    -1 3 -1    // 最左一侧为ε的转换
    6 -1 -1    // 其余列按照输入的字符集的顺序填写
    -1 -1 5    // 有多个转换状态时用 , 分隔(不加空格)
    6 -1 -1
    1,7 -1 -1
    -1 8 -1
    9,11 -1 -1
    -1 10 -1
    13 -1 -1
    -1 -1 12
    13 -1 -1
    -1 -1 -1
    

    DFA格式与NFA相同

    子集构造算法和DFA最小化算法的实现

    输入部分
    NFA在程序中的存储:
    const int MAXN = 105;
    
    char c_set[MAXN]; // 字符集
    int c_set_len;    // 字符集长度
    
    int state[MAXN]; // 状态集合
    int state_len;   // 状态个数
    
    int done_state_nfa[MAXN]; // 结束状态集合
    int done_state_nfa_len; // 结束状态个数
    int start_state_nfa;	// 起始状态
    
    unordered_map<char, vector<int>> NFA_STATE[MAXN]; // NFA转移表
    

    集合的表示采用64位整形,每位代表一个状态,为1则该状态在集合中。

    结束状态由于不止有一个,所以使用一个数组存储(这里的存储方式不再是每位表示一个状态集合,而是直接保存状态的编号),起始状态保存方式相同。

    使用哈希表构造NFA的转移表,由于是非确定状态机,所以每一个状态对应的输出可能有多个转移,所以使用vetcor数组存放转移到的状态。具体表示含义如下:

    NFA_STATE[i][c]: 第i个状态在输入为c的情况下的转移
    
    将输入格式转换为NFA的存储形式
        printf("输入字符集中的字符个数: ");
        scanf("%d", &c_set_len);
        c_set_len++;
        c_set[0] = '#';
        printf("输入字符集: (不要加空格)");
        scanf("%s", c_set + 1);
        c_set[c_set_len] = '\0';
    

    读取字符集,首先读取字符的个数来分配空间,给第一个字符留空,表示ϵ\epsilon,使用#表示,其余依次读取输入的字符

    	printf("输入状态个数: (状态从0递增开始)");
        scanf("%d", &state_len);
        for (int i = 0; i < state_len; i++) {
            state[i] = i;
        }
    
        printf("起始状态为0\n");
        start_state_nfa = 0;
    

    状态的编号默认从0开始递增,所以只需输入状态的总数,默认起始状态为0

        printf("输入结束状态个数: ");
        scanf("%d", &done_state_nfa_len);
        printf("输入结束状态: ");
        for (int i = 0; i < done_state_nfa_len; i++) {
            int a;
            scanf("%d", &a);
            if (a >= state_len) {
                printf("不合法\n");
                i--;
            } else
                done_state_nfa[i] = a;
        }
    

    输入结束状态,要判断是否合法:即是不是存在的状态,不存在则不可输入,否则放入结束状态集中。

        printf("输入转移表: \n");
        for (int i = 0; i < state_len; i++) {
            for (int j = 0; j < c_set_len; j++) { // 解析输入的状态字符串
                string nxt;
                vector<int> ret;
                cin >> nxt;
                if (nxt.find(",") == string::npos) {
                    ret.push_back(stoi(nxt));
                } else {
                    int idx = 0;
                    while (nxt.find(",") != string::npos) {
                        idx = nxt.find(",");
                        string num = nxt.substr(0, idx);
                        ret.push_back(stoi(num));
                        idx++;
                        nxt = nxt.substr(idx);
                    }
                    ret.push_back(stoi(nxt));
                }
                NFA_STATE[i][c_set[j]] = ret;
            }
        }
    

    输入转移表的部分。首先以字符串的形式读入,因为要解析字符串,把以’,‘分隔的数字读出。解析字符串时,判断有没有’,‘(line 7-9),没有则直接进行转换,调用stoi函数转换为整型;如果有,则循环寻找’,’,并且切割出子串,转换为整型,直到没有’,’,在剩余字符串中(line 10-18),最后将这一个vector数组放到对应的状态的输入转移中。

    读入部分完成。

    子集构造算法
    DFA在程序中的存储
    int done_state_dfa[MAXN]; // 结束状态集合
    int done_state_dfa_len;
    int start_state_dfa[MAXN]; // 其实只有一个起始状态,这里没必要使用数组。
    int start_dfa_len;
    
    unordered_map<char, int> DFA_STATE[MAXN]; // DFA状态
    unordered_map<int, int> DFA_NFA;
    int mark[MAXN];
    int dfa_state_len;
    

    与NFA不同的是,由于DFA是确定的,所以对于某一个字符的转移只有一个下一状态。

    DFA_NFA表示NFA的状态和DFA的状态相对应的形式,即一个DFA状态是由哪个NFA状态得到的。

    mark数组表示DFA的状态有没有被标记过

    算法步骤

    从初始状态出发,计算ϵclosure\epsilon-closure,作为新的状态A

    标记状态A,对每个输入求move(A,c)move(A, c),再求其ϵclosure\epsilon-closure,如果是个新的状态,则加入到DFA状态集合中,同时更新Dtran[A,c]=BDtran[A,c] = B状态转移表

    当所有状态都被标记后,算法结束。

    ϵclosure\epsilon-closure计算方法
    int epsilon_closure(int state) { // state位表示状态
        int ans = 0;
        vector<int> state_; // 得到的状态集合
        int cnt = 0;
        for (int i = 1; i <= (1 << state_len); i <<= 1, cnt++) {
            if (state & i) {
                state_.push_back(cnt);
                ans |= i;
            }
        }
        for (auto v : state_) { // 对该状态集合中每个状态求 ε闭包
            for (auto vec : NFA_STATE[v][c_set[0]]) {
                if (vec != -1) {
                    ans |= (1 << vec);
                }
            }
        }
        return ans;
    }
    

    首先从状态集合state中取出包含的状态(line 5-10),之后,对每个状态求ϵ\epsilon的转移,根据NFA转移表得到下一状态,加入到状态集合ans中(line 11 - 17),最后返回状态集合ans

    由于这只是单步的ϵclosure\epsilon-closure,而要求的为无限多步,所以

        int closure = epsilon_closure(init_state);
        while (closure != epsilon_closure(closure)) {
            closure = epsilon_closure(closure);
        }
    

    一直计算,直到闭包不再变化,此时得到了所有的ϵclosure\epsilon-closure

    movemove计算方法
    int move(int state, char c) { // state位表示状态 c为当前输入字符
        int ans = 0;
        vector<int> state_;
        int cnt = 0;
        for (int i = 1; i <= (1 << state_len); i <<= 1, cnt++) {
            if (state & i)
                state_.push_back(cnt);
        }
        for (auto v : state_) {
            for (auto vec : NFA_STATE[v][c]) {
                if (vec != -1) {
                    ans |= (1 << vec);
                }
            }
        }
        return ans;
    }
    

    ϵclosure\epsilon-closure相似,只不过对于转移得到的状态,不再是ϵ\epsilon,而是对于当前的输入字符。同样的,先从状态集合state中抽出状态放到state_中,之后找到转移得到的状态,放入新状态集合ans中,返回ans

    子集构造算法具体实现

    初始化部分:

        done_state_dfa_len = 0;
        dfa_state_len = 0;
        start_dfa_len = 0;
        memset(mark, 0, sizeof(mark));
        set<int> already_exist;
        int init_state = 1;
    

    首先将DFA相关的值赋值为0,将mark数组置0,mark数组用于标记是不是还有DFA的状态没被标记,already_exist集合用于判断是不是已经存在当前状态;init_state为1,由于起始状态为0,所以状态集合的最低位为1,十进制表示为1。

        int closure = epsilon_closure(init_state);
        while (closure != epsilon_closure(closure)) {
            closure = epsilon_closure(closure);
        }
    

    初始的计算闭包

        for (int k = 0; k < done_state_nfa_len; k++) {
            if (closure & (1 << done_state_nfa[k])) {
                done_state_dfa[done_state_dfa_len++] = dfa_state_len;
                break;
            }
        }
        if (closure & (1 << start_state_nfa)) {
            start_state_dfa[start_dfa_len++] = dfa_state_len;
        }
        DFA_NFA[dfa_state_len++] = closure;
    

    首先判断这一个ϵclosure\epsilon-closure是不是结束状态,如果包含了NFA的结束状态,那么对应的DFA的结束状态要进行设置,对于起始状态的处理也是同样的。(line 1-9)

    之后,DFA的0状态对应于这一个ϵclosure\epsilon-closure,放到DFA_NFA中

    	int all_marked = 0;
        while (!all_marked) { // 全都被标记过,结束
            int i;
            for (i = 0; i < dfa_state_len; i++) { // 找第一个未被标记的状态
                if (mark[i] == 0) {
                    mark[i] = 1;
                    break;
                }
            }
            if (i == dfa_state_len) { // 未找到,全被标记
                all_marked = 1;
                continue;
            }
    
    

    这里进行while循环,如果所有DFA状态都被标记,那么可以结束,all_marked为1,结束循环。否则找到第一个未标记的状态进行标记。

            int now_nfa_state = DFA_NFA[i]; // 得到对应的NFA状态
            already_exist.insert(now_nfa_state);
    

    通过找到的第一个未被标记的状态得到NFA对应的状态集合,并将其插入到已存在中,那么接下来就是对其求ϵclosure\epsilon-closure和move步了。

            for (int j = 1; j < c_set_len; j++) {              // 遍历所有输入
                int new_state = move(now_nfa_state, c_set[j]); // move步
                int closure = epsilon_closure(new_state);      // closure步
                while (closure != epsilon_closure(closure)) {
                    closure = epsilon_closure(closure);
                }
    

    首先求对输入的move步,得到新状态再求ϵclosure\epsilon-closure

    			if (closure == 0) { // 没有对应的转换
                    DFA_STATE[i][c_set[j]] = {-1};
                }
    

    如果closure = 0的话,表示没有对应的转换,那么将转移表中该项设置为-1

    			else {
                    if (already_exist.find(closure) == already_exist.end()) { // 转换的状态不存在
                        already_exist.insert(closure);                        // 加入到set中
                        if (closure & (1 << start_state_nfa)) {
                            start_state_dfa[start_dfa_len++] = dfa_state_len;
                        }
                        for (int k = 0; k < done_state_nfa_len; k++) {
                            if (closure & (1 << done_state_nfa[k])) {
                                done_state_dfa[done_state_dfa_len++] = dfa_state_len;
                                break;
                            }
                        }
                        DFA_NFA[dfa_state_len++] = closure; // 有了一个新的DFA状态
                    }
    

    否则的话,如果当前的状态不存在,则发现了一个新状态,插入到set中,并且判断是不是结束状态,是不是起始状态(line 4-12),再将他对应的DFA,NFA状态插入DFA_NFA的对应关系表中。

                    // 向当前状态当前输入的转换中添加新状态
                    int k;
                    for (k = 0; k < dfa_state_len; k++) { // 找要添加的DFA状态
                        if (DFA_NFA[k] == closure) {
                            break;
                        }
                    }
                    DFA_STATE[i][c_set[j]] = k;
    

    在这之后,就可以更新DFA的转移表,首先找到这一个新状态 k 的编号,放到状态 i 在 c[j] 的转移下

    完整代码
    int epsilon_closure(int state) { // state位表示状态
        int ans = 0;
        vector<int> state_; // 得到的状态集合
        int cnt = 0;
        for (int i = 1; i <= (1 << state_len); i <<= 1, cnt++) {
            if (state & i) {
                state_.push_back(cnt);
                ans |= i;
            }
        }
        for (auto v : state_) { // 对该状态集合中每个状态求 ε闭包
            for (auto vec : NFA_STATE[v][c_set[0]]) {
                if (vec != -1) {
                    ans |= (1 << vec);
                }
            }
        }
    
        return ans;
    }
    int move(int state, char c) { // state位表示状态 c为当前输入字符
        int ans = 0;
        vector<int> state_;
        int cnt = 0;
        for (int i = 1; i <= (1 << state_len); i <<= 1, cnt++) {
            if (state & i)
                state_.push_back(cnt);
        }
        for (auto v : state_) {
            for (auto vec : NFA_STATE[v][c]) {
                if (vec != -1) {
                    ans |= (1 << vec);
                }
            }
        }
        return ans;
    }
    void getDFA() {
        done_state_dfa_len = 0;
        dfa_state_len = 0;
        start_dfa_len = 0;
        memset(mark, 0, sizeof(mark));
        set<int> already_exist;
        int init_state = 1;
        int closure = epsilon_closure(init_state);
        while (closure != epsilon_closure(closure)) {
            closure = epsilon_closure(closure);
        }
        for (int k = 0; k < done_state_nfa_len; k++) {
            if (closure & (1 << done_state_nfa[k])) {
                done_state_dfa[done_state_dfa_len++] = dfa_state_len;
                break;
            }
        }
        if (closure & (1 << start_state_nfa)) {
            start_state_dfa[start_dfa_len++] = dfa_state_len;
        }
        DFA_NFA[dfa_state_len++] = closure;
        int all_marked = 0;
        while (!all_marked) { // 全都被标记过,结束
            int i;
            for (i = 0; i < dfa_state_len; i++) { // 找第一个未被标记的状态
                if (mark[i] == 0) {
                    mark[i] = 1;
                    break;
                }
            }
            if (i == dfa_state_len) { // 未找到,全被标记
                all_marked = 1;
                continue;
            }
    
            int now_nfa_state = DFA_NFA[i]; // 得到对应的NFA状态
            already_exist.insert(now_nfa_state);
            for (int j = 1; j < c_set_len; j++) {              // 遍历所有输入
                int new_state = move(now_nfa_state, c_set[j]); // move步
                int closure = epsilon_closure(new_state);      // closure步
                while (closure != epsilon_closure(closure)) {
                    closure = epsilon_closure(closure);
                }
                if (closure == 0) { // 没有对应的转换
                    DFA_STATE[i][c_set[j]] = {-1};
                } else {
                    if (already_exist.find(closure) == already_exist.end()) { // 转换的状态不存在
                        already_exist.insert(closure);                        // 加入到set中
                        if (closure & (1 << start_state_nfa)) {
                            start_state_dfa[start_dfa_len++] = dfa_state_len;
                        }
                        for (int k = 0; k < done_state_nfa_len; k++) {
                            if (closure & (1 << done_state_nfa[k])) {
                                done_state_dfa[done_state_dfa_len++] = dfa_state_len;
                                break;
                            }
                        }
                        DFA_NFA[dfa_state_len++] = closure; // 有了一个新的DFA状态
                    }
                    // 向当前状态当前输入的转换中添加新状态
                    int k;
                    for (k = 0; k < dfa_state_len; k++) { // 找要添加的DFA状态
                        if (DFA_NFA[k] == closure) {
                            break;
                        }
                    }
                    DFA_STATE[i][c_set[j]] = k;
                }
            }
        }
    }
    

    验证部分放在最后

    DFA最小化算法
    最小化DFA在程序中的存储
    int done_state_mindfa[MAXN];
    int done_state_mindfa_len;
    int start_state_mindfa[MAXN];
    int start_mindfa_len;
    
    unordered_map<char, int> minDFA_STATE[MAXN]; // minDFA状态
    unordered_map<int, int> minDFA_DFA;			// minDFA和DFA的对应关系
    int fa[MAXN];								// 用于DFA集合的划分
    int minDFA_len;
    

    这里多增加了一个fa数组,用于在做最小化时,判断一个集合内的这些DFA状态转移方向是否相同。

    其余与之前DFA相同。

    算法步骤

    在这里插入图片描述

    接受状态和非接受状态
    int findEnd() {
        int ans = 0;
        for (int i = 0; i < done_state_dfa_len; i++) {
            ans |= (1 << done_state_dfa[i]);
        }
        return ans;
    }
    

    由于最初的划分要分为这两个状态集,所以根据DFA的结束状态,很轻松的就可以找到一个结束状态集,根据存储状态的方式和集合的性质,可以使用:

        int end = findEnd();
        int netend = (1 << (dfa_state_len)) - 1 - end;
    

    来得到非接收状态。

    初始化部分
        if (netend == 0) {
            minDFA_DFA[0] = end;
            minDFA_len = 1;
        } else {
            minDFA_DFA[0] = netend;
            minDFA_DFA[1] = end;
            minDFA_len = 2;
        }
    

    由于存在一种可能:只有接收状态,所以要进行判断。

    fa数组的作用
    void set_fa() {
        for (int i = 0; i < minDFA_len; i++) {
            int state = minDFA_DFA[i];
            int cnt = 0;
            for (int j = 1; j <= (1 << dfa_state_len); j <<= 1, cnt++) {
                if (state & j) {
                    fa[cnt] = i;
                }
            }
        }
        return;
    }
    

    从最小化DFA和DFA对应的关系中,可以得到minDFA状态的编号,将其对应的DFA的状态的fa值均设置为其编号,用于在之后进行判断这一个DFA集是不是可分得。这里只需要注意fa数组的含义:fa[i] 编号为i的DFA状态在哪个minDFA状态集中

    DFA最小化算法具体实现
        for (int i = 0; i < minDFA_len; i++) {
            if (divide(minDFA_DFA[i], i)) {
                i--;
            }
        }
    

    当所有集合均不可分时,则结束,否则当前仍是可分得,所以使i - 1,相当于回溯的过程。

    判断划分以及是否可分的实现:

    int divide(int state, int idx) {
        vector<int> divide_list[minDFA_len + 1];
    
        vector<int> state_;
        int cnt = 0;
        for (int i = 1; i <= (1 << state_len); i <<= 1, cnt++) {
            if (state & i) {
                state_.push_back(cnt);
            }
        }
    

    从当前的minDFA状态集合中抽取出DFA的状态,放到state_中

        int ret = 0;
        for (int c = 1; c < c_set_len; c++) {
            for (int i = 0; i <= minDFA_len; i++) {
                divide_list[i].clear();
            }
            char input = c_set[c];
    

    对于每个输入input,进行判断其集合是不是可分

            for (auto v : state_) {
                int nxt = DFA_STATE[v][input];
                if (nxt == -1) {
                    divide_list[minDFA_len].push_back(v);
                    continue;
                }
                int set = fa[nxt];
                divide_list[set].push_back(v);
            }
    

    对于每一个状态,得到其在当前输入下的转移nxt,要注意的是,nxt = -1即没有转移时,也算是一种可分情况,这时将其放入到divide_list的最后一个元素而不是放到fa[nxt]的位置;否则都放入divide_list中fa[nxt]的位置,表示这些DFA状态转移到了fa[nxt]的minDFA状态。

    		int cnt = 0;
            for (int i = 0; i <= minDFA_len; i++) {
                if (divide_list[i].size() != 0)
                    cnt++;
            }
            if (cnt == 1) {
                continue;
            }
    

    之后判断,如果只有一个divide_list不为空,则表示不可分,继续查看下一个输入。

    		else {
                int len = minDFA_len;
                int ret = 0;
                for (int i = 0; i <= len; i++) {
                    if (divide_list[i].size() != 0 && ret != 0) {
                        minDFA_DFA[minDFA_len++] = cal_Set(divide_list[i]);
                    }
                    else if (divide_list[i].size() != 0 && ret == 0) {
                        minDFA_DFA[idx] = cal_Set(divide_list[i]);
                        ret++;
                    }
                }
                set_fa();
                return 1;
            }
    

    否则可分,对于找到的第一个divide_list新集合,把他放到当前的集合的位置,因为当前集合已经被拆开了,之后对于每一个新集合,扩张minDFA状态,放入其中。并在最后更新fa数组,返回1,进行回溯。cal_Set是根据状态计算状态集合

    如果最后返回了0,那么表示不可分,算法结束。

    转移表和接收状态起始状态的获取
    void getTrans() {
        for (int i = 0; i < minDFA_len; i++) {
            int set = minDFA_DFA[i];
            int cnt = 0;
            int ret = 0;
            for (int k = 1; k <= (1 << dfa_state_len); k <<= 1, cnt++) {
                if (set & k)
                    break;
            }
            for (int c = 0; c < c_set_len; c++) {
                char input = c_set[c];
                int nxt = DFA_STATE[cnt][input];
                if (nxt == -1)
                    minDFA_STATE[i][input] = -1;
                else
                    minDFA_STATE[i][input] = fa[nxt];
            }
        }
    }
    

    对于转移表,抽取出minDFA对应的当前DFA的状态集合,这一部分由于对于每一个输入,所有状态的转移是一样的,所有只需找一个DFA状态即可。之后得到DFA转移表中,当前状态在当前输入下的转移,找到其fa的位置,即对应的minDFA的转移,放入转移表中。

    void getDone_StartState() {
        done_state_mindfa_len = 0;
        start_mindfa_len = 0;
        for (int i = 0; i < minDFA_len; i++) {
            int set = minDFA_DFA[i];
            for (int k = 0; k < done_state_dfa_len; k++) {
                if (set & (1 << done_state_dfa[k])) {
                    done_state_mindfa[done_state_mindfa_len++] = i;
                    break;
                }
            }
            for (int k = 0; k < start_dfa_len; k++) {
                if (set & (1 << start_state_dfa[k])) {
                    start_state_mindfa[start_mindfa_len++] = i;
                    break;
                }
            }
        }
    }
    

    获取接收状态和起始状态与DFA相同,不再细说。

    完整代码
    int findEnd() {
        int ans = 0;
        for (int i = 0; i < done_state_dfa_len; i++) {
            ans |= (1 << done_state_dfa[i]);
        }
        return ans;
    }
    int cal_Set(vector<int> ret) {
        int ans = 0;
        for (auto v : ret) {
            ans |= (1 << v);
        }
        return ans;
    }
    void set_fa() {
        for (int i = 0; i < minDFA_len; i++) {
            int state = minDFA_DFA[i];
            int cnt = 0;
            for (int j = 1; j <= (1 << dfa_state_len); j <<= 1, cnt++) {
                if (state & j) {
                    fa[cnt] = i;
                }
            }
        }
        return;
    }
    int divide(int state, int idx) {
        vector<int> divide_list[minDFA_len + 1];
    
        vector<int> state_;
        int cnt = 0;
        for (int i = 1; i <= (1 << state_len); i <<= 1, cnt++) {
            if (state & i) {
                state_.push_back(cnt);
            }
        }
        // for (auto v: state_) cout << v << " ";
        // cout << endl;
        int ret = 0;
        for (int c = 1; c < c_set_len; c++) {
            for (int i = 0; i <= minDFA_len; i++) {
                divide_list[i].clear();
            }
            char input = c_set[c];
            for (auto v : state_) {
                int nxt = DFA_STATE[v][input];
                if (nxt == -1) {
                    divide_list[minDFA_len].push_back(v);
                    continue;
                }
                int set = fa[nxt];
                divide_list[set].push_back(v);
            }
            int cnt = 0;
            for (int i = 0; i <= minDFA_len; i++) {
                // cout << i << "->" << divide_list[i].size() << endl;
                if (divide_list[i].size() != 0)
                    cnt++;
            }
            if (cnt == 1) {
                continue;
            } else {
                int len = minDFA_len;
                int ret = 0;
                for (int i = 0; i <= len; i++) {
                    if (divide_list[i].size() != 0 && ret != 0) {
                        minDFA_DFA[minDFA_len++] = cal_Set(divide_list[i]);
                    }
                    else if (divide_list[i].size() != 0 && ret == 0) {
                        minDFA_DFA[idx] = cal_Set(divide_list[i]);
                        ret++;
                    }
                }
                set_fa();
                return 1;
            }
        }
        return 0;
    }
    void getTrans() {
        for (int i = 0; i < minDFA_len; i++) {
            int set = minDFA_DFA[i];
            int cnt = 0;
            int ret = 0;
            for (int k = 1; k <= (1 << dfa_state_len); k <<= 1, cnt++) {
                if (set & k)
                    break;
            }
            // cout << "cnt: " << cnt << " ";
            for (int c = 0; c < c_set_len; c++) {
                char input = c_set[c];
                int nxt = DFA_STATE[cnt][input];
                if (nxt == -1)
                    minDFA_STATE[i][input] = -1;
                else
                    minDFA_STATE[i][input] = fa[nxt];
            }
        }
    }
    void getDone_StartState() {
        done_state_mindfa_len = 0;
        start_mindfa_len = 0;
        for (int i = 0; i < minDFA_len; i++) {
            int set = minDFA_DFA[i];
            for (int k = 0; k < done_state_dfa_len; k++) {
                if (set & (1 << done_state_dfa[k])) {
                    done_state_mindfa[done_state_mindfa_len++] = i;
                    break;
                }
            }
            for (int k = 0; k < start_dfa_len; k++) {
                if (set & (1 << start_state_dfa[k])) {
                    start_state_mindfa[start_mindfa_len++] = i;
                    break;
                }
            }
        }
    }
    void minDFA() {
        int end = findEnd();
        int netend = (1 << (dfa_state_len)) - 1 - end;
        if (netend == 0) {
            minDFA_DFA[0] = end;
            minDFA_len = 1;
        } else {
            minDFA_DFA[0] = netend;
            minDFA_DFA[1] = end;
            minDFA_len = 2;
        }
        set_fa();
        for (int i = 0; i < minDFA_len; i++) {
            if (divide(minDFA_DFA[i], i)) {
                i--;
            }
        }
        getTrans();
        getDone_StartState();
    }
    

    实验结果验证

    测试样例1:

    正则表达式:(a|b)*abb(a|b)*

    NFA输入

    2
    ab
    18
    1
    17
    1,7 -1 -1
    2,4 -1 -1
    -1 3 -1
    6 -1 -1
    -1 -1 5
    6 -1 -1
    1,7 -1 -1
    -1 8 -1
    -1 -1 9
    -1 -1 10
    11,17 -1 -1
    12,14 -1 -1
    -1 13 -1
    16 -1 -1
    -1 -1 15
    16 -1 -1
    11,17 -1 -1
    -1 -1 -1
    

    输出的转移表及对应关系

    NFA转移表
    	#	a	b	
    0	1,7	-1	-1	
    1	2,4	-1	-1	
    2	-1	3	-1	
    3	6	-1	-1	
    4	-1	-1	5	
    5	6	-1	-1	
    6	1,7	-1	-1	
    7	-1	8	-1	
    8	-1	-1	9	
    9	-1	-1	10	
    10	11,17	-1	-1	
    11	12,14	-1	-1	
    12	-1	13	-1	
    13	16	-1	-1	
    14	-1	-1	15	
    15	16	-1	-1	
    16	11,17	-1	-1	
    17	-1	-1	-1	
    DONE STATE: 17 
    START STATE: 0
    
    DFA-NFA
    DFA	NFA	
    0	{0,1,2,4,7,}
    1	{1,2,3,4,6,7,8,}
    2	{1,2,4,5,6,7,}
    3	{1,2,4,5,6,7,9,}
    4	{1,2,4,5,6,7,10,11,12,14,17,}
    5	{1,2,3,4,6,7,8,11,12,13,14,16,17,}
    6	{1,2,4,5,6,7,11,12,14,15,16,17,}
    7	{1,2,4,5,6,7,9,11,12,14,15,16,17,}
    8	{1,2,4,5,6,7,10,11,12,14,15,16,17,}
    
    DFA转移表
    	a	b	
    0	1	2	
    1	1	3	
    2	1	2	
    3	1	4	
    4	5	6	
    5	5	7	
    6	5	6	
    7	5	8	
    8	5	6	
    DONE STATE: 4 5 6 7 8 
    START STATE: 0 
    
    minDFA-DFA
    minDFA	DFA	
    0	{0,2,}
    1	{4,5,6,7,8,}
    2	{3,}
    3	{1,}
    
    minDFA转移表
    	a	b	
    0	3	0	
    1	1	1	
    2	3	1	
    3	3	2	
    DONE STATE: 1 
    START STATE: 0 
    

    使用随机生成样例进行测试:

    /* (a|b)*abb(a|b)* */
    #include <iostream>
    #include <random>
    #include <time.h>
    using namespace std;
    
    int main() {
        srand(time(0));
        freopen("../input_file/input3_", "w", stdout);
        char s[2] = {'a', 'b'};
        for (int i = 0; i <= 4; i++) {
            for (int times = 0; times < 3; times++) {
                for (int j = 0; j < i; j++) {
                    int choice = rand() % 2;
                    cout << s[choice];
                }
                cout << "abb";
                for (int j = 0; j < i; j++) {
                    int choice = rand() % 2;
                    cout << s[choice];
                }
            }
            cout << endl;
        }
        for (int num = 0; num < 9; num++) {
            int times = rand() % 15 + 1;
            for (int i = 0; i < times; i++) {
                int choice = rand() % 2;
                cout << s[choice];
            }
            cout << endl;
        }
    }
    

    生成的输入字符串:

    abbabbabb
    babbbaabbababba
    aaabbaabbabbbbbbabbba
    bababbaabaababbaabbababbaba
    bbbaabbbbabbabbabbbabaabbbabbbbba
    ba
    aaaaaaababaaa
    babbaaa
    aabaab
    bbaaabbbbbaa
    b
    babbaaabbbba
    ab
    bbbabaa
    

    输出结果:

    abbabbabb:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    babbbaabbababba:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    aaabbaabbabbbbbbabbba:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    bababbaabaababbaabbababbaba:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    bbbaabbbbabbabbabbbabaabbbabbbbba:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    ba:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    aaaaaaababaaa:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    babbaaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    aabaab:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    bbaaabbbbbaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    b:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    babbaaabbbba:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    ab:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    bbbabaa:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    

    可以看出三种状态机同为ACCEPT或FAIL。

    测试样例2:

    正则表达式:(a|b)*a(a|b)

    NFA输入

    2
    ab
    14
    1
    13
    1,7 -1 -1
    2,4 -1 -1
    -1 3 -1
    6 -1 -1
    -1 -1 5
    6 -1 -1
    1,7 -1 -1
    -1 8 -1
    9,11 -1 -1
    -1 10 -1
    13 -1 -1
    -1 -1 12
    13 -1 -1
    -1 -1 -1
    

    输出的转移表及对应关系

    NFA转移表
    	#	a	b	
    0	1,7	-1	-1	
    1	2,4	-1	-1	
    2	-1	3	-1	
    3	6	-1	-1	
    4	-1	-1	5	
    5	6	-1	-1	
    6	1,7	-1	-1	
    7	-1	8	-1	
    8	9,11	-1	-1	
    9	-1	10	-1	
    10	13	-1	-1	
    11	-1	-1	12	
    12	13	-1	-1	
    13	-1	-1	-1	
    DONE STATE: 13 
    START STATE: 0
    
    DFA-NFA
    DFA	NFA	
    0	{0,1,2,4,7,}
    1	{1,2,3,4,6,7,8,9,11,}
    2	{1,2,4,5,6,7,}
    3	{1,2,3,4,6,7,8,9,10,11,13,}
    4	{1,2,4,5,6,7,12,13,}
    
    DFA转移表
    	a	b	
    0	1	2	
    1	3	4	
    2	1	2	
    3	3	4	
    4	1	2	
    DONE STATE: 3 4 
    START STATE: 0 
    
    minDFA-DFA
    minDFA	DFA	
    0	{0,2,}
    1	{3,}
    2	{1,}
    3	{4,}
    
    minDFA转移表
    	a	b	
    0	2	0	
    1	1	3	
    2	1	3	
    3	2	0	
    DONE STATE: 1 3 
    START STATE: 0 
    

    使用随机生成样例进行测试:

    /* (a|b)*a(a|b) */
    #include <iostream>
    #include <random>
    #include <time.h>
    using namespace std;
    
    int main() {
        srand(time(0));
        freopen("../input_file/input1_", "w", stdout);
        char s[2] = {'a', 'b'};
        for (int i = 0; i <= 4; i++) {
            for (int times = 0; times < 3; times++) {
                for (int j = 0; j < i; j++) {
                    int choice = rand() % 2;
                    cout << s[choice];
                }
                cout << 'a';
                int choice = rand() % 2;
                cout << s[choice] << endl;
            }
        }
        for (int num = 0; num < 8; num++) {
            int times = rand() % 7 + 1;
            for (int i = 0; i < times; i++) {
                int choice = rand() % 2;
                cout << s[choice];
            }
            cout << endl;
        }
    }
    

    生成的输入字符串:

    ab
    ab
    aa
    bab
    aaa
    bab
    bbaa
    aaab
    aaaa
    bbbab
    abbab
    abbaa
    aabbaa
    abaaaa
    baaaaa
    bb
    bbaa
    abbbb
    bbb
    ba
    a
    bbaba
    aba
    

    输出结果:

    ab:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    ab:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    aa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    bab:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    aaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    bab:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    bbaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    aaab:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    aaaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    bbbab:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    abbab:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    abbaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    aabbaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    abaaaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    baaaaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    bb:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    bbaa:
    NFA ACCEPT
    DFA ACCEPT
    minDFA ACCEPT
    
    abbbb:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    bbb:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    ba:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    a:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    bbaba:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    
    aba:
    NFA FAIL
    DFA FAIL
    minDFA FAIL
    

    通过上面测试可以看出,程序正确

    关于源码使用提示 或 见README.md

    generator: 随机生成对应的正则表达式的正例字符串和反例字符串

    生成哪一组测试样例即调用相应的 input*_roll.cc 程序即可

    input_file: 输入文件

    input*: 输入的NFA图

    输入格式:

    2              // 输入的字符集的个数
    ab             // 字符集 中间无空格
    14             // NFA状态总数n:编号从0开始到n-1,默认起始状态为0
    1              // 终结状态个数
    13             // 终结状态编号
    1,7 -1 -1      // 一下n行输入当前状态的转换
    2,4 -1 -1      // 无转换用-1代替
    -1 3 -1        // 最左一侧为ε的转换
    6 -1 -1        // 其余列按照输入的字符集的顺序填写
    -1 -1 5        // 有多个转换状态时用 , 分隔(不加空格)
    6 -1 -1
    1,7 -1 -1
    -1 8 -1
    9,11 -1 -1
    -1 10 -1
    13 -1 -1
    -1 -1 12
    13 -1 -1
    -1 -1 -1
    

    input*_: 构造出的测试样例

    output_file: 输出文件

    out*: 输出的NFA DFA minDFA的状态转移表,以及对应的状态集合,终结状态集合

    check*: 用于比对输入的测试样例能否被接受,ACCEPT为接受,FAIL为不可接受

    Exp2.cc: 实验二文件

    使用时,请注意宏定义的声明,使用哪一组输入文件即定义如:

    // 使用input1以及input1_:
    #define TEST_CASE_1
    // 使用input2以及input2_:
    #define TEST_CASE_2
    // 使用input3以及input3_:
    #define TEST_CASE_3
    

    只能声明1 2 3中的一个

    完整实验代码

    见文章开始的链接

    展开全文
  • 实验三 NFA确定化和DFA最小化

    千次阅读 2017-11-25 21:35:54
    (一)NFA–>DFA(2小时)一、实验目的学习掌握将NFA转为DFA的子集构造法。二、实验任务(1)存储NFA与DFA; (2)编程实现子集构造法将NFA转换成DFA。三、实验内容(1)确定NFA与DFA的存储格式。 要求为3个以上...
  • 一、实验标题:NFA确定化和DFA最小化 二、实验目的:1. 学习和掌握将NFA转为DFA的子集构造法。2. 学会编程实现等价划分法最小化DFA。 三、实验内容:(一)NFA确定化(1)确定NFA与DFA的存储格式。要求为3个以上...
  • 编译原理实现DFA和NFA,C语言 (凑字数字数字数字数字数)
  • 第一部分 NFA确定化 一、实验目的 学习掌握将NFA转为DFA的子集构造法。 二、实验任务 (1)存储NFA与DFA; (2)编程实现子集构造法将NFA转换成DFA。 三、实验内容 (1)确定NFA与DFA的存储格式。 要求为3个...
  • 编译原理实验三:NFA确定化和DFA最小化

    千次阅读 多人点赞 2019-01-29 20:59:42
    学习掌握将NFA转为DFA的子集构造法。 实验任务 (1)存储NFA与DFA; (2)编程实现子集构造法将NFA转换成DFA。 实验内容 (1)确定NFA与DFA的存储格式。要求为3个以上测试NFA准备好相应有限自动机的存储...
  • ps:实验要求文件的推荐 NFA 数据格式有大问题,对于NFA来说,因为NFA对于一个字符可能有多个转移状态,所以推荐的格式不能全部储存到。本人写的时候以为避开了雷,However,没注意替换成了状态转移表...学习掌握将N
  • 本资源为一个src文件夹,有四个package: 1. Beans:NFA的DFA类 2.Utils:用于输入和输出的工具类 3.Service:核心代码。提供了确定化和最小化的代码实现 4.Test:可直接运行、测试(并且提供测试样例)

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 127
精华内容 50
关键字:

dfa确定化和最小化