DFA转化为NFA DFA的确定化 代码实现

#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn=;
int vis[maxn];
vector<set<int> >C;//构造出的子集
map<set<int>,int> flag;//子集是否被标记
map<int,map<int,map<char,int> > > nfa;
struct DFA
{
    int st;
    char w;
    int ed;
};
vector<DFA> dfa;

int n,m;//状态数和弧的数量

//状态集T的c弧转换
set<int> Move(set<int> T,char c)
{
    set<int> U;
    for(set<int>::iterator i=T.begin();i!=T.end();i++)
    {
        int u=*i;
        for(int j=;j<n;j++)
        {
            if(nfa[u][j][c]==)
                U.insert(j);
        }
    }
    return U;
}
//状态集T的e-闭包
set<int> eclosure(set<int> T)
{
    set<int> U;
    queue<int> Q;
    for(set<int>::iterator i=T.begin();i!=T.end();i++)
    {
        U.insert(*i);
        Q.push(*i);
    }
    //BFS寻找经任意条e弧可到达的状态
    memset(vis,,sizeof(vis));
    while(!Q.empty())
    {
        int v=Q.front();
        Q.pop();
        for(int i=;i<n;i++)
        {
            if(nfa[v][i]['e']&&vis[i]==)
            {
                U.insert(i);
                Q.push(i);
                vis[i]=;
            }
        }
    }
    return U;
}

int main()
{
    freopen("input.txt","r",stdin);
    cin>>n>>m;
    n++;
    //构造状态图
    for(int i=;i<m;i++)
    {
        int u,v;
        char w;
        cin>>u>>v>>w;
        nfa[u][v][w]=;
    }
    int k0=;//K0
    set<int> temp;
    temp.insert(k0);
    temp=eclosure(temp);
    C.push_back(temp);
    //子集构造算法
    while()
    {
        int st=-;
        set<int> T;
        //判断C中是否存在被标记的子集T
        for(int i=;i<C.size();i++)
        {
            if(!flag[C[i]])
            {
                st=i;
                T=C[i];
                break;
            }
        }
        if(st==-)
            break;
        flag[T]=;//标记T
        set<int> U=eclosure(Move(T,'a'));
        if(!flag[U])
        {
            C.push_back(U);
        }
        //懒得写转换函数了，就在这里得出转换结果
        for(int i=;i<C.size();i++)
        {
            if(U==C[i])
            {
                dfa.push_back(DFA{st,'a',i});
                break;
            }
        }
        U=eclosure(Move(T,'b'));
        if(!flag[U])
        {
            C.push_back(U);
        }
        for(int i=;i<C.size();i++)
        {
            if(U==C[i])
            {
                dfa.push_back(DFA{st,'b',i});
                break;
            }
        }
    }
    //输出构造的子集
    cout<<"共构造了"<<C.size()<<"个子集:"<<endl;
    for(int i=;i<C.size();i++)
    {
        set<int> T=C[i];
        cout<<"T"<<i<<"={";
        for(set<int>::iterator j=T.begin();j!=T.end();j++)
        {
            if(j!=T.begin())
                cout<<',';
            cout<<*j;
        }
        cout<<"}"<<endl;
    }
    cout<<endl;
    cout<<"构造的DFA M如下:"<<endl<<endl;
    cout<<"S={";
    for(int i=;i<C.size();i++)
    {
        if(i!=)
            cout<<",";
        cout<<"[T"<<i<<"]";
    }
    cout<<"}"<<endl<<endl;
    for(int i=;i<dfa.size();i++)
    {
        cout<<"D([T"<<dfa[i].st<<"],"<<dfa[i].w<<")=[T"<<dfa[i].ed<<"]"<<endl;
    }
    return ;
}
           

输入测试数据

input.txt

格式如下

10 13
0 1 e
1 2 e
2 3 a
3 6 e
1 4 e
4 5 b
5 6 e
6 1 e
6 7 e
7 8 a
8 9 b
9 10 b
0 7 e