目录(?)[+]
完整引擎代码在github上，地址为：https://github.com/sun2043430/RegularExpression_Engine.git
DFA最小化的算法原理
“DFA状态最小化算法的工作原理是将一个DFA的状态集合分划成多个组，每个组中的各个状态之间相互不可区分。然后，将每个组中的状态合并成状态最少DFA的一个状态。算法在执行过程中维护了状态集合的一个分划，分划中的每个组内的各个状态不能区分，但是来自不同组的任意两个状态是可区分的。当任意一个组不能再被分解为更小的组时，这个分划就不能再进一步精化，此时我们就得到了状态最少的DFA。”
——《编译原理》例3.38
起始时，该分划包含两个组：接受状态组和非接受状态组。
实例
如图（编译原理 图3-36）
首先我们将ABCDE分划到两个组中{ABCD}和{E}，{E}是接受状态组，且不可被再分割。
{ABCD}是可分割的，所以我们考虑所有可能的转换。
先看转换字符a：
A->a->B
B->a->B
C->a->B
D->a->B
所以ABCD经过a到达的集合是{B}，而{B}属于{ABCD}这一个集合，所以我们说{ABCD}在输入字符为a时是不可分划的。
在来看转换字符b：
A->b->C
B->b->D
C->b->C
D->b->E
到达的集合是{CDE}，其中CD属于{ABCD}分划，E属于{E}分划。
所以我们说{ABCD}在输入字符为b时是不可分划的。按照输入b转换到的组，我们将{ABCD}分划为{ABC}和{D}两个组。同时将{ABCD}从组集合中删除。因为{ABCD}已经分划为{ABC}和{D}。
接下来看{ABC}，先看在字符a上的转换：
A->a->B
B->a->B
C->a->B
因为全部都是到达的B，所以不可分划。
再看在字符b上的转换：
A->b->C
B->b->D
C->b->C
其中C属于{ABC}组，D属于{D}组。所以{ABC}可以分划为{AC}和{B}。最后看{AC}组，A和C在字符a上都转换到B，在字符b上都转换到C，所以{AC}是不可分划的组。
最后得到的分组情况为：
{AC}，{B}，{D}，{E}。
同一个组中只需要保留一个节点即可（因为同一个组的节点在转换上都是相同的），所以我们直接将C节点去除，保留A节点（因为A节点是开始状态节点）。最终得到的状态最小DFA的转换表为：
代码实现（关键代码）
- BOOLCDFA::FindRelationNode(list<DFANodeRelation>&lstNodeRelation,
- intnIdxFrom,unsignedcharch,int&nMapToIdx)
- {
- list<DFANodeRelation>::iteratorit=lstNodeRelation.begin();
- for(;it!=lstNodeRelation.end();it++)
- {
- if(it->m_nIdxFrom==nIdxFrom&&it->m_ch==ch)
- nMapToIdx=it->m_nIdxTo;
- returnTRUE;
- }
- }
- returnFALSE;
- intCDFA::FindIdxInListSet(intnMapToIdx,list<set<int>>&lstSet)
- inti=0;
- for(list<set<int>>::iteratorit=lstSet.begin();it!=lstSet.end();it++,i++)
- set<int>&setIdx=*it;
- for(set<int>::iteratoritInt=setIdx.begin();itInt!=setIdx.end();itInt++)
- if(nMapToIdx==*itInt)
- returni;
- return-1;
- BOOLCDFA::PartitionOneGroup(list<set<int>>&lstSet,set<int>&setoneGroup,85); line-height:18px"> list<DFANodeRelation>&lstNodeRelation,
- map<int,87); background-color:inherit; font-weight:bold">int>>&mapPartitionInfo)
- BOOLbRet=FALSE;
- list<DFANodeRelation>::iteratoritRelation;
- set<unsignedchar>setChar;
- set<int>setMapToIdx;
- try
- //collecteachnode'stranslationcharintheset
- for(set<int>::iteratorit=setoneGroup.begin();it!=setoneGroup.end();it++)
- for(itRelation=lstNodeRelation.begin();itRelation!=lstNodeRelation.end();itRelation++)
- if(itRelation->m_nIdxFrom==*it)
- setChar.insert(itRelation->m_ch);
- //endcollect
- for(set<unsignedchar>::iteratorit=setChar.begin();it!=setChar.end();it++)
- mapPartitionInfo.clear();
- intnMapToIdx=-1;//indicatemaptoadeadstate,therenotranslationforthispairofnode/char
- int>::iteratoritNodeId=setoneGroup.begin();itNodeId!=setoneGroup.end();itNodeId++)
- if(FindRelationNode(lstNodeRelation,*itNodeId,*it,nMapToIdx))
- intnIdx=FindIdxInListSet(nMapToIdx,lstSet);
- if(nIdx==-1)
- assert(FALSE);
- mapPartitionInfo[nIdx].insert(*itNodeId);
- else
- mapPartitionInfo[-1].insert(*itNodeId);
- if(mapPartitionInfo.size()>1)//haddistinguish
- break;
- catch(...)
- gotoExit0;
- bRet=TRUE;
- Exit0:
- returnbRet;
- BOOLCDFA::PartitionGroups(list<set< list<set<int>>::iteratorit=lstSet.begin();
- int>>mapPartitionInfo;
- //usedmaptorecordthenodecantranslatetowhichgroup,
- //theint(mapkey)isgroupid.
- //theset<int>containthenodeIDthatcantranslatetothegroup.
- for(;it!=lstSet.end();)
- mapPartitionInfo.clear();
- int>&setoneGroup=*it;
- CHECK_BOOL(PartitionOneGroup(lstSet,setoneGroup,lstNodeRelation,mapPartitionInfo));
- //meansthatcurrentgroupcanpartition
- int>>::iteratoritM=mapPartitionInfo.begin();
- for(;itM!=mapPartitionInfo.end();itM++)
- lstSet.push_back(itM->second);
- catch(...)
- gotoExit0;
- it=lstSet.erase(it);//ifagrouphadpartition,thegroupneeddeleteinthelist
- it++;
- /**
- @briefMinimizeDFA
- @paramnSetSizenodecount
- @paramlstNodeRelationnoderelationtable
- @paramsetAcceptingIdxsetforAcceptingstatusnode'sindex
- @paramlstSetforsavetheresult
- @returnTRUE,success;otherwisemeansfail.
- */
- BOOLCDFA::MinimizeDFA(intnNodeCount,87); background-color:inherit; font-weight:bold">int>&setAcceptingIdx,87); background-color:inherit; font-weight:bold">int>>&lstSet
- )
- int>setUnAccepting;
- assert(nNodeCount>=1);
- assert(setAcceptingIdx.size()!=0);
- assert(lstNodeRelation.size()!=0);
- lstSet.clear();
- lstSet.push_back(setAcceptingIdx);
- //getunAcceptingset
- for(inti=0;i<nNodeCount;i++)
- if(setAcceptingIdx.find(i)==setAcceptingIdx.end())
- setUnAccepting.insert(i);
- if(setUnAccepting.size()>0)
- lstSet.push_back(setUnAccepting);
- CHECK_BOOL(PartitionGroups(lstSet,lstNodeRelation));
- returnbRet;
- }
完整引擎代码在github上，地址为： https://github.com/sun2043430/RegularExpression_Engine.git