nfa-dfa.cpp

实现从nfa到dfa的转换

#include <fstream>
#include <iostream>
#include <memory>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <set>
using namespace std;

/*
从NFA -> DFA
步骤：
1.将所有还未计算的集合计算完（初始时，讲开始点s所在集合 设为未计算集合）
2.对于每个未计算的集合计算 每条边 (a,b) ，如果产生一个新的完全不同的set，就把他加入集合中。
3.如何计算一个新产生的set呢？ 按照e边扩展。

!!子集构造法按照书的P26, 用栈来实现，队列其实也行,深搜也行

e-closure (e的闭包) 计算按书上方法栈, floodfill 方法也行
*/

typedef set<int> SI;
typedef vector<int> VI;
typedef pair<SI::iterator , bool > PI;

const int N = 10000;
VI g[N][300];//g[i][j] 表示对于点 i 经过符号 j 到达的点,有向
int n=0,m=0;//点数，边的种类数
int e_edge=-1;//记录e边的编号
char edge[300];//每个 边的编号 对应的字符
int original[N];//对应的原编号

int v[300];//存 某个字符是否用过, 用过的话，就是它对应的标记号
int v2[N];//存 某个数字是否用过，用过的话，就是它对应的标记号


int start;
VI end;

//以下为保存DFA结果
int rg[N][300];
SI rset[N];
int n2;//n2 集合数   ;边的种类数 应该保持不变，除了e边
int begin2=0;//起始和结束集合
VI end2;
void debug_show_set( SI &s)
{
    for ( SI::iterator si = s.begin(); si!=s.end();si++ )
          cout<<*si<<" ";
}


void inputing() //读入边，转化为矩阵
{
    int i,a,b,r;
    char ch;

    memset(v,-1,sizeof(v));
    memset(v2,-1,sizeof(v2));

    cout<<"边的数目：";cin>>r;
    for (i=0;i<r;i++)
    {
          cin>>a>>ch>>b;
          if (-1==v2[ a ])
          {
                original[ n ] = a;
                v2[a] = n++;
          }
          a = v2[a];
          if (-1==v2[ b ])
          {
                original[ n ]= b;
                v2[b] = n++;
          }
          b = v2[b];
          if ( -1==v[ ch ] )
          {
                edge[m] = ch;
                v[ch] = m++;
          }
          if (ch == 'e')
			e_edge = v[ch];
          ch = v[ch];
          g[ a ][(int)ch].push_back(b);
    }
    cout<<"e_edge is "<<e_edge<<endl;//debug
    cout<<"起点";cin>>start;
    start = v2[start];
    cout<<"终点数目 及各终点";cin>>a;
    for (i=0;i<a;i++)
    {
          cin>>b;
          b = v2[b];
          end.push_back( b );
    }
}

SI e_closure( SI & s)// 求 s 的 e的闭包 栈 方法
{
    SI r = s;
	SI::iterator  si;
    int stack[N],top=0;
    memset(stack,0,sizeof(stack));

    for (si = s.begin();si!=s.end();si++)
    {
          stack[top++] = *si;
    }

    //begin stack
    while (top)
    {
          top--;
          int i,j;
          j = stack[top];
          PI p1;//pair类型， 第二个参数是bool
          for (i=0;i<g[ j ][ e_edge ].size();i++ )
          {
                p1 = r.insert( g[ j ][ e_edge ][ i ] );
                if (p1.second == true)
                {
                      stack[top++] = g[ j ][ e_edge ][i];
                }
          }
    }
    return r;
}

SI move( SI & s,int j )//用 j 编号的边走一步
{
    SI r;
    SI :: iterator si;
    for (si = s.begin();si!=s.end();si++)
          for (int i=0;i<g[ *si ][ j ].size();i++ )
          {
                int temp;
                temp = g[*si][j][i];
                r.insert( temp );
          }
    return r;
}

bool contain_end(const SI & s)
{
    int i;
    for (i=0;i<end.size();i++)
    if ( s.find( end[ i ] ) != s.end() )
		return 1;
    return 0;
}


void find_sub_set()
{
    int stack[N],top;
    memset(stack,0,sizeof(stack));
	top = 0;
    SI temp;
    temp.insert(start);
    rset[ n2++ ] = e_closure( temp );
    cout<<"begin with :";
	debug_show_set(rset[0]);
	cout<<endl;
    stack[top++] = 0;
    if (contain_end( rset[0] ) ) 
		end2.push_back(0);
    while ( top )
    {
          top--;
          int begin = stack[top];
          for (int i=0;i<m;i++)//对每个输入符号 （边）都计算，应排除e边
          if (i!=e_edge)
          {
                temp = rset[ begin ];
                SI move_set = move(temp , i );
                if (move_set.size() <=0)//如果对于某条边没有 输出的集合，应该不用计算
                continue;
                rset[n2] = e_closure( move_set );
                int j;
                for (j=0;j<n2;j++)
                {
                      if ( rset[n2] == rset[ j ] )
                      break;
                }

                if (j!=n2)
                {
                      rg[begin][i] = j;//不管是否产生新的子集，relation一定要记录
                      cout<<"A NEW EDGE AT RESULT IS "<<begin<<" ["<<edge[i]<<"] "<<j<<endl;//debug
                      continue;
                }

                rg[ begin ][ i ] = n2 ;
                cout<<"A NEW EDGE AT RESULT IS "<<begin<<" ["<<edge[i]<<"] "<<n2<<endl;//debug

                cout<<"FIND NEW SET :";debug_show_set( rset[n2] );cout<<endl;//debug
                if (contain_end( rset[n2] ) )//检查是否包含结束状态
                {
                      end2.push_back( n2 );
                      cout<<"END";//debug
                }
                stack[top++] = n2;
                n2++;
          }
    }
}

void outputing()
{
    int i,j;
    cout<<endl;
    for ( i=0;i<n2;i++ )
    {
          cout<<"set "<<i<<" : contain original status: ";
          for (SI::iterator si=rset[ i ].begin(); si!=rset[ i ].end(); si++ )
                cout<<original[ *si ]<<" ";
          if ( start == i )
          cout<<" start";
          if ( find(end2.begin(),end2.end() , i ) !=end2.end() )
          cout<<" end";
          cout<<endl;
    }
    cout<<"realtions : "<<endl;
    cout<<"    ";
    for (i=0;i<m;i++)
    if (i!=e_edge)
          cout<<edge[i]<<" ";
    cout<<endl;
    for ( i=0;i<n2;i++ )
    {
          cout<<char(i+'A')<<" ";
          for (j=0;j<m;j++)
          if (j==e_edge)
          continue;
          else if (rg[i][j]!=-1 )cout<<" "<<char('A'+rg[i][j])<<" ";
          else cout<<" "<<'X'<<" ";
          cout<<endl;
    }
}

/*
如果遇到错误则终止判断，
如果在\0终止则判断 终止时的状态
不在 \0 终止 则一定不合法
*/
void work()
{
  char str[N];
  cout<<" 输入串 ";cin>>str;
  int i,j;
  int now;//目前状态
  now = 0;

  while (i<strlen(str) && now!=-1)
  {
      int temp = v[ str[ i ] ];
      cout<<"to judge i "<<i<<" "<<str[i]<<" edge num:"<<temp<<endl;//debug
      now = rg[now][temp];
      i++;
  }
  if (str[i] == '\0')
  {
        if ( find(end2.begin(),end2.end(),now) != end2.end() )
        {
            cout<<"ANSWER IS TRUE"<<endl;
        }
        else cout<<"ANSWER IS WRONG"<<endl;
  }
  else cout<<"ANSWER IS WRONG"<<endl;
}




int main()
{
      inputing();
      memset(rg,-1,sizeof(rg));
      find_sub_set();
      outputing();
      work();
      return 0;
}