編譯原理(二) NFA的確定化及DFA的最小化的算法及C++實現 · 編譯原理算法實現

## 1. NFA的確定化 ### 1.１. 明確NFA的定義一個非確定的有窮自動機(NFA)M是一個五元式： - M=(S,∑,δ,S0,F) - S是一個有限集，它額每個元素稱為一個狀態。 - ∑是一個有窮字母表，它的每個元素稱為一個輸入字符 - δ是一個從S×∑?至S子集額單值映射。即：δ:S×∑?→2?S - S0?S,是一個非空的初態集 - F? S , 是一個終態集(可空) ### 1.2. 定義運算定義對狀態集合I的幾個有關運算： - 狀態集合I的ε-閉包，表示為ε-closure(I)，定義為一狀態集，是狀態集I中的任何狀態s經任意條ε弧而能到達的狀態的集合。狀態集合I的任何狀態s都屬于ε-closure(I)。 - 狀態集合I的a弧轉換，表示為move(I,a)定義為狀態集合J，其中J是所有那些可從I的某一狀態經過一條a弧而到達的狀態的全體。定義Ia = ε-closure(move(I,a)) ### 1.3. 算法描述 - 每次從隊頭取出一個集合，**(開始隊列內只有初態集合I的ε-閉包(I) )**，然后得到它對于任意一個字符a的Ia=ε?closure(move(I,a)) - 然后如果當前狀態之前沒有出現過，那么當前狀態作為一個新的狀態I,放入隊列。 - 一直做如上操作，直到隊列為空 ### 1.4. 代碼如下： ~~~ #include <iostream> #include <cstdio> #include <algorithm> #include <fstream> #include <queue> #include <vector> #include <string> #include <cstring> #include <set> #define MAX 500 #define M 1000007 using namespace std; struct Set { set<int> elements; int state; }I[MAX]; vector<int> e[MAX]; vector<int> edge[MAX]; vector<int> val1[MAX]; vector<int> val2[MAX]; vector<int> hash[M]; vector<int> types; int vis[MAX][MAX]; int cntp,cnts,start,finish,used[MAX]; void _clear( ); void clear( ); void _add( int u , int v , int x ); void add( int u , int v , int x ); void dfs ( set<int>& elements , int u , int d , int flag ); void ensure(); void minimize(); int get_hash( set<int>& item ); //#define DEBUG int main ( ) { int m; puts("給出NFA的邊的條數:"); while ( ~scanf ( "%d" , &m ) ) { _clear(); clear(); puts("給出NFA的始態和終態:"); scanf ( "%d%d" , &start , &finish ); puts("給出所有的邊，每行一條:"); for ( int i = 0 ; i < m ; i++ ) { int u,v,x; scanf ( "%d%d%d" , &u , &v , &x ); _add ( u , v , x ); } #ifdef DEBUG set<int> temp; int num[]={2,3,6,7,8}; //for ( int i = 2 ; i < 6 ; i++ ) // dfs ( temp , i , 0 , 2 ); for ( int i = 0 ; i < 5 ; i++ ) dfs ( temp , num[i] , 0 , 1 ); set<int>::iterator it = temp.begin(); for ( ; it != temp.end() ; it++ ) printf ( "%d " , *it); puts(""); #else ensure(); puts("計算結果如下:"); printf ( "%d\n" , cnts ); for ( int i = 0 ; i < cnts ; i++ ) for ( int j = 0 ; j < edge[i].size() ; j++ ) printf ( "edges : %d %d %d\n" , i , edge[i][j] , val2[i][j] ); puts("\n給出DFA的邊的條數:"); #endif } } void _clear() { for ( int i = 0 ; i < MAX ; i++ ) { e[i].clear(); val1[i].clear(); } types.clear(); memset ( used , 0 , sizeof ( used ) ); } void clear() { for ( int i = 0 ; i < MAX ; i++ ) { edge[i].clear(); val2[i].clear(); } } void _add ( int u , int v , int x ) { e[u].push_back ( v ); val1[u].push_back ( x ); if ( !used[x] ) { types.push_back ( x ); used[x] = types.size(); } } int get_hash ( set<int>& item ) { int sum = 0; set<int>::iterator it = item.begin(),it1,it2; for ( ; it!= item.end() ; it++ ) { sum += (*it)*(*it)%M; sum %= M; } for ( int i = 0 ; i < hash[sum].size() ; i++ ) { int x = hash[sum][i]; set<int>& temp = I[x].elements; it = temp.begin(); bool flag = true; if ( temp.size() != item.size() ) continue; for ( it1 = temp.begin() , it2 = item.begin(); it2!= item.end() ; it1++,it2++ ) if ( *it1 != *it2 ) { flag = false; break; } if ( flag ) return x; } return -1; } int make_hash ( set<int>& item ) { int sum = 0; set<int>::iterator it = item.begin(); for ( ; it!= item.end() ; it++ ) { sum += (*it)*(*it)%M; sum %= M; } hash[sum].push_back ( cnts ); return cnts++; } void add ( int u , int v , int x ) { edge[u].push_back ( v ); val2[u].push_back ( x ); } void dfs ( set<int>& elements , int u , int d , int flag ) { if ( vis[u][d] ) return; vis[u][d] = 1; if ( d == 1 ) elements.insert ( u ); if ( d == 2 ) return; int len = e[u].size(); for ( int i = 0 ; i < len ; i++ ) { int v = e[u][i],dd; int x = val1[u][i]; if ( x == flag ) dd = d+1; else if ( x == 0 ) dd = d; else continue; dfs ( elements , v , dd , flag ); } } void ensure ( ) { I[0].elements.insert(start); cnts = 1; for ( int i = 0 ; i < cnts ; i++ ) { set<int>& cur = I[i].elements; for ( int j = 0 ; j < types.size() ; j++ ) { if ( types[j] == 0 ) continue; memset ( vis , 0 , sizeof ( vis ) ); set<int>& temp = I[cnts].elements; temp.clear(); set<int>::iterator it = cur.begin(); for ( ; it != cur.end() ; it++ ) dfs ( temp , *it , 0 , types[j] ); if ( temp.empty() ) continue; int x = get_hash ( temp ); if ( x == -1 ) x = make_hash ( temp ); add ( i , x , types[j] ); } set<int>::iterator it = cur.begin(); printf ( "I%d :" , i ); for ( ; it!= cur.end() ; it++ ) printf ( "%d " , *it ); puts (""); } } ~~~ ## 2. DFA的最小化 ### 2.1. 明確DFA的定義一個確定的有窮自動機(DFA)M是一個五元式： - M=(S, ∑, δ, s0, F)其中 - S是一個有限集，它的每個元素稱為一個狀態。 - ∑是一個有窮字母表，它的每個元素稱為一個輸入字符－δ是一個從S×∑至S的單值映射。δ(s,a)=s’意味著：當現行狀態－為s、輸入字符為a時，將轉換到下一個狀態s’。我們稱s’為s的一個后繼狀態。 - s0∈S，是唯一的初態。 - F ? S，是一個終態集（可空） ### 2.2 算法描述 - DFA M =（K,∑,f, k0,, kt),最小狀態DFA M’ - 1.構造狀態的初始劃分∏0：終態kt 和非終態K- kt兩組 - 2.對∏施用傳播性原則構造新劃分∏new - 3.如∏new=∏,則令∏new=∏并繼續步驟4，否則∏:=∏new重復2 - 4.為∏final中的每一組選一代表，這些代表構成M’的狀態。若k是一代表且f(k,a)=t,令r是t組的代表，則M’中有一轉換f’(k,a)=r M’ 的開始狀態是含有K0的那組的代表 M’的終態是含有Kt的那組的代表 - 5.去掉M’中的死狀態. ### 2.3 代碼實現 ~~~ #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> #include <string> #include <vector> #include <map> #include <queue> #include <fstream> #define MAX 507 using namespace std; struct Node { int x; int type; Node(){} Node( int a , int b ) :x(a),type(b){} bool operator < ( const Node& a ) const { return type < a.type; } }; int mp[MAX][MAX]; vector<int> _edge[MAX]; vector<int> _val[MAX]; vector<int> edge[MAX]; vector<int> val[MAX]; vector<int> point; vector<pair<int,int> > ans1; vector<int> ans2; vector<Node> col; int fa[MAX]; int type[MAX]; int state[MAX]; int used[MAX]; int kinds; int groups_num; int n; int m; void init (); int _find( int x ); void _union ( int x , int y ); void _add ( int u , int v , int x ); void add ( int u , int v , int x ); void minimize ( ); void make_csv(); int main ( ) { init ( ); scanf ( "%d%d" , &n , &m ); for ( int i = 1 ; i <= n ; i++ ) scanf ( "%d" , &type[i] ); for ( int i = 0 ; i < m ; i++ ) { int u,v,x; scanf ( "%d%d%d" , &u , &v , &x ); _add ( u ,v , x ); } minimize(); //最小化后的點的保留結果 puts ("points : " ); printf ( "%d\n" , (int)point.size() ); for ( int i = 0 ; i < point.size(); i++ ) printf ( "%d " , point[i] ); puts(""); //最小化后的邊的保留結果 puts ( "edge: "); m = ans1.size(); for ( int i = 0 ; i < ans1.size() ; i++ ) printf ( "%d %d %d\n" , ans1[i].first , ans1[i].second , ans2[i] ); puts(""); make_csv(); } void init ( ) { for ( int i = 0 ; i < MAX ; i++ ) { edge[i].clear(); _edge[i].clear(); } point.clear(); memset ( type , 255 , sizeof ( type ) ); memset ( used , 0 , sizeof ( used ) ); kinds = 0; groups_num = 2; col.clear(); for ( int i = 0 ; i < MAX ; i++ ) fa[i] = i; } void _add ( int u , int v , int x ) { _edge[u].push_back ( v ); _val[u].push_back ( x ); if ( used[x] ) return ; used[x] = x; kinds++; } void add ( int u , int v , int x ) { edge[u].push_back ( v ); val[u].push_back ( x ); } int _find ( int x ) { return x == fa[x]? x: fa[x] = _find ( fa[x] ); } void _union ( int x , int y ) { x = _find ( x ); y = _find ( y ); fa[x] = y; } void minimize ( ) { queue<vector<Node> > q[2]; col.clear(); for ( int i = 1 ; i <= n ; i++ ) { if ( type[i] == 0 ) col.push_back ( Node( i , 0 ) ); } q[1].push ( col ); col.clear(); for ( int i = 1 ; i <= n ;i++ ) { if ( type[i] == 1 ) col.push_back ( Node ( i , 1 ) ); } q[1].push( col ); col.clear(); for ( int i = 1 ; i <= kinds ; i++ ) { int cur = i%2; int next = (i+1)%2; while ( !q[next].empty() ) q[next].pop(); while ( !q[cur].empty() ) { vector<Node> front = q[cur].front(); q[cur].pop(); for ( int j = 0 ; j < front.size() ; j++ ) { Node& temp = front[j]; int u = temp.x; for ( int k = 0 ; k < _edge[u].size() ; k++ ) { int v = _edge[u][k]; int x = _val[u][k]; if ( x != i ) continue; temp.type = type[v]; } } sort ( front.begin() , front.end() ); if ( front[0].type == front[front.size()-1].type ) q[next].push ( front ); else { col.clear(); col.push_back ( front[0] ); for ( int j = 1 ; j < front.size() ; j++ ) { if ( front[j].type != front[j-1].type ) { q[cur].push ( col ); col.clear(); groups_num++; } type[front[j].x] = groups_num; col.push_back ( front[j] ); } q[cur].push( col ); } } } //#define DEBUG #ifdef DEBUG int id = (kinds+1)%2; int num = 1; while ( !q[id].empty() ) { vector<Node> temp = q[id].front(); q[id].pop(); printf ( "%d : ", num++ ); for ( int i = 0 ; i < temp.size() ; i++ ) printf ( "%d " , temp[i].x ); puts(""); } #else int id = (kinds+1)%2; while ( !q[id].empty() ) { vector<Node> temp = q[id].front(); q[id].pop(); for ( int i = 1 ; i < temp.size() ; i++ ) _union ( temp[i].x , temp[i-1].x); } memset ( used , 0 , sizeof ( used ) ); memset ( mp , 0 , sizeof ( mp ) ); for ( int i = 1 ; i <= n ;i++ ) { int x = _find(i); if ( used[x] ) continue; used[x] = 1; point.push_back ( x ); } ans1.clear(); for ( int i = 1 ; i <= n ; i++ ) for ( int j = 0 ; j < _edge[i].size() ; j++ ) { int v = _edge[i][j]; int x = _val[i][j]; int a = _find(i); int b = _find(v); if ( mp[a][b] ) continue; mp[a][b] = 1; add ( a , b , x ); ans1.push_back ( make_pair ( a , b ) ); ans2.push_back ( x ); } #endif } void make_csv ( ) { freopen ( "g1.csv" , "w" , stdout ); printf ( "%d,%d, \n" , n , m ); for ( int i = 0 ; i < point.size() ; i++ ) if ( i == 0 ) printf ( "%d" , point[i] ); else printf ( ",%d" , point[i] ); puts(""); for ( int i = 0 ; i < m ; i++ ) printf ( "%d,%d,%d\n" , ans1[i].first , ans1[i].second , ans2[i] ); fclose(stdout); } ~~~