mindfa.cpp

编译原理课程设计之正则表达式与自动机之间的变换

/*
确定有限自动机的化简
DFA的最小化算法-DFA M =（K,∑,f, k0,, kt),最小状态DFA M'                                       
1.构造状态的一初始划分 ：终态kt 和非终态K- kt两组(group)
2.对∏施用Partition过程构造新划分∏new 
3. 如∏new  =∏,则令 ∏final=∏ 并继续步骤4，否则∏:=∏new重复2 .
4.为∏final中的每一组选一代表，这些代表构成M'的状态。若k是一代表且f(k,a)=t,令r是t组的代表，
则M'中有一转换f'(k,a)=r,M' 的开始状态是含有S0的那组的代表， M' 的终态是含有F的那组的代表
5.去掉M'中的无用状态（即从初态开始永远到达不了的那些状态）.
确定有限自动机的化简
过程Partition 
For  ∏ 中的每个组 G  do
begin         
1. 把 G  分为若干个子组，使得G 中的两个状态 s  和 t  在同一个子组中，
当且仅当对于所有输入符号 a,  状态 s  和 t  转换状态在 ∏  中同一个组中;
2. 用新生成的子组代替 G  ，构成新的划分 ∏new
end	
*/

#include "Globals.h"

int RRR=20;

STATE_LIST* MinDFAStateArray=NULL;//最小化DFA状态集查询表
NODE_LIST* MinDFAtransArray=NULL;//最小化DFA状态转换表
int MinDFAStateNum=0;//DFA状态总数
bool* IsAccept=NULL;

CPoint* States1;

void ClearMinDFA()
{
	if(MinDFAStateArray!=NULL)
	{
		delete []MinDFAStateArray;
		MinDFAStateArray=NULL;
	}
	if(MinDFAtransArray!=NULL)
	{
		delete []MinDFAtransArray;
		MinDFAtransArray=NULL;
	}
	if(IsAccept!=NULL)
	{
		delete []IsAccept;
		IsAccept=NULL;
	}
}

bool FindState(STATE_LIST& T,State state)//在状态集T中查找状态state
{
	bool flag=0;
	STATE_LIST::iterator iter;
	for(iter=T.begin();iter!=T.end();iter++)
	{
		if(*iter==state)//如果找到返回true,否则返回false
		{
			flag=1;
			break;
		}
	}
	return flag;
}



int GetStateListIndex(list<STATE_LIST>& H,State state,char r)//状态state经过r转换
//所到达的状态在划分H的某一组中,返回该组在H中的索引,即第几组
{
	int index;
	bool flag=0;
	State temp;
	NODE_LIST::iterator iter;
	list<STATE_LIST>::iterator iter1;
	
	//对DFA转换表搜索
	for(iter=DFAtransArray[state].begin();iter!=DFAtransArray[state].end();iter++)
	{
		if(iter->symbol==r)//如果symbol==r,do
		{
			temp=iter->state;
			flag=1;
			break;
		}
	}
	if(flag==0)//如果找不到返回-1
	{
		return -1;
	}
	for(index=0,iter1=H.begin();iter1!=H.end();iter1++,index++)
	{
		if(FindState(*iter1,temp))
		{
			break;
		}
	}
	return index;//如果找到,返回该索引
}

State Get_r_State(NODE_LIST*& DFAtransArray,State state,char r)//返回状态经过r所到达的状态
{
	State result=-1;
	NODE_LIST::iterator iter;
	for(iter=DFAtransArray[state].begin();iter!=DFAtransArray[state].end();iter++)
	{
		if(iter->symbol==r)
		{
			result=iter->state;
			break;
		}
	}
	return result;
}

int GetStateListIndex(STATE_LIST*& MinDFAStateArray,State& T)//返回状态链表某项的索引
{
	int i;
	for(i=0;i<MinDFAStateNum;i++)
	{
		if(FindState(MinDFAStateArray[i],T))
		{
			break;
		}
	}
	return i;
}

void MinDFA()
{
	int i,index,size;
	STATE_LIST temp;
	STATE_LIST F,S_F;//F为接受状态集,s_F为非接受状态集
	list<STATE_LIST> H;//定义一个STATE_LIST链表H作为当
	//前划分,其元素是STATE_LIST,即:当前划分的各组状态集
	list<STATE_LIST>::iterator iter,iter0;//遍历当前划分的指针
	LETTER_LIST::iterator iter1;//遍历字母表的指针
	STATE_LIST::iterator iter2,iter3;//遍历状态表的指针

	F=acceptlist;//把接受状态付给F
	for(i=0;i<DFAStateNum;i++)
	{
		if(!FindState(F,i))//如果是非接受状态集S_F添加一项
		{
			S_F.push_back(i);
		}
	}
	if(!S_F.empty())
	H.push_back(S_F);//将非接受状态集加入划分H
	if(!F.empty())
	H.push_back(F);//将接受状态集加入划分H
	S_F.clear();//清空S_F
	F.clear();//清空F,释放内存
	//这样,初始划分就只有两个状态集S_F,F

	for(iter=H.begin();iter!=H.end();)//遍历整个划分的各个组
	{
		bool flag=0;//形成新划分的标志
		for(iter1=letterlist.begin();iter1!=letterlist.end();
		    iter1++)//遍历整个字母表,
		//检测每个字母对H中每一组的划分
		{
			for(iter2=iter->begin();iter2!=iter->end();iter2++)
			{
				index=GetStateListIndex(H,*iter2,*iter1);
				temp.push_back(index);
			}//对某组的所有状态进行此操作:
			//搜索划分H中的各组状态集,返回改组的索引,
			//将所有的索引用一个链表保存起来,
			//以便后来对该组进行划分
			size=H.size();
			STATE_LIST* statelist=new STATE_LIST[size+1];
			for(iter3=temp.begin(),iter2=iter->begin();
			iter3!=temp.end();iter3++,iter2++)
			{
				if(*iter3==-1)
				{
					statelist[size].push_back(*iter2);
				}
				else
				{
					statelist[*iter3].push_back(*iter2);
				}
			}//对索引号进行分组
			temp.clear();
			int num=0;
			for(i=0;i<=size;i++)//统计有多少组不为空,用num保存
			{
				if(!statelist[i].empty())
				{
					num++;
				}
			}
			if(num>1)//如果多于一组,就进行划分
			{
				iter0=iter++;
				iter0->clear();
				H.erase(iter0);//将原来的组从划分中删掉
				for(i=0;i<=size;i++)
				{
					if(!statelist[i].empty())
				//将改组的划分添加到原来的划分H中,形成新的划分
					{
						H.insert(iter,statelist[i]);
						statelist[i].clear();
					}
				}
				delete []statelist;//释放内存
				iter=H.begin();//对新的划分从头开始进行检测,是否可以再分
				flag=1;//形成新划分的标志
				break;
			}
			else
			{
				delete []statelist;//释放内存
			}
		}
		if(flag==1)//如果形成新划分,就不执行iter++
		{
			continue;
		}
		iter++;
	}//到此,划分完成
	//以下是将划分中的等价组,以一个索引进行标记,处理转换问题
	Node node;
	State checkstate;
	MinDFAStateNum=H.size(); 
	MinDFAStateArray=new STATE_LIST[MinDFAStateNum];
	MinDFAtransArray=new NODE_LIST[MinDFAStateNum];
	//多申请一个数组保存该索引的状态是否为接受状态
	IsAccept=new bool[MinDFAStateNum];
	for(iter=H.begin(),i=0;iter!=H.end();iter++,i++)
	{
        MinDFAStateArray[i]=*iter;
 	   //检测接受状态
		if(FindState(acceptlist,*(iter->begin())))
		{
			IsAccept[i]=1;
		}
		else
		{
			IsAccept[i]=0;
		}
	}
	H.clear();
	for(i=0;i<MinDFAStateNum;i++)
	{
		for(iter1=letterlist.begin();
		iter1!=letterlist.end();iter1++)
		{
			for(iter2=MinDFAStateArray[i].begin();
			iter2!=MinDFAStateArray[i].end();iter2++)
			{
			    checkstate=Get_r_State(DFAtransArray,*iter2,*iter1);
				if(checkstate!=-1)
				{
					node.symbol=*iter1;
					node.state=GetStateListIndex(MinDFAStateArray,checkstate);
		            MinDFAtransArray[i].push_back(node);
					break;
				}
			}
		}
	}

}

//画最小化DFA图
void PaintMinDFA(CDC* pDC,CAutoMakeView3*pView)
{
	CPen* pNewPen=new CPen(PS_SOLID,2,RGB(0,0,0));
	CBrush* pNewBrush=new CBrush(RGB(255,255,255));
	CPen* pOldPen=pDC->SelectObject(pNewPen);
	CBrush* pOldBrush=pDC->SelectObject(pNewBrush);
	pDC->SetBkMode(TRANSPARENT);
    
	CPoint pt,pt1;
	CString str;
	int i,j;//j用来记录某一状态有多少自己的转换

	NODE_LIST::iterator iter;
	LETTER_LIST::iterator iter1;

	States1=new CPoint[MinDFAStateNum];

	for(i=0;i<MinDFAStateNum;i++)//确定各个状态的结点位置
	{
		//画各个结点
		if(i==0)
		{
			States1[i].x=50;
	        States1[i].y=300;
		}
		else
		{
			States1[i].x=States1[i-1].x+100;
		    States1[i].y=States1[i-1].y;
		}
		str.Format("%d",i);
		pView->OnPrepareDC(pDC);	
		pt=States1[i];
		CRect rc(pt.x-RRR,pt.y-RRR,pt.x+RRR,pt.y+RRR);
		pDC->Ellipse(&rc);
		if(IsAccept[i]==true)
		{
			rc.SetRect(pt.x-RRR+3,pt.y-RRR+3,pt.x+RRR-3,pt.y+RRR-3);
			pDC->Ellipse(&rc);
		}
		pDC->DrawText(str,&rc,DT_SINGLELINE|DT_VCENTER|DT_CENTER);
	}

	for(i=0;i<MinDFAStateNum;i++)////////////////画状态转换的曲线
	{
		j=1;
		for(iter=MinDFAtransArray[i].begin();
		iter!=MinDFAtransArray[i].end();iter++)
		{
			pt=States1[i];
			pt1=States1[iter->state];
			if(pt==pt1)
			{
				DrawArc(pDC,pt,RRR,j,iter->symbol);
				j++;
			}
			else
			{
                DrawArc(pDC,pt,pt1,RRR,iter->symbol);
			}
		}
	}
}