一、实验课题
| A004 |
模拟DFA |
编写一个程序，模拟最少状态的确定有限自动机，判断输入串能否识别。 |
首先根据某个词法构建最少状态的确定有限自动机，然后输入字符串，判断该字符串能否被上述自动机识别。
我们选择的词法具体形式如下：
S∑={d，.，e，+，-},则∑上的正规式d*(.dd*|ε)(e(+|-|ε)dd*|ε)，这表示的是无符号数的集合。其中d为0~9的数字。
二、设计思想
我们需要编写一个能识别形如正规式d*(.dd*|ε)(e(+|-|ε)dd*|ε)的无符号数，且构建的自动机是最少状态的确定有限自动机。
正则式与有穷自动机具有等价性，即
1.对于∑上的一个NFAM，可以构造一个∑上的正规式R,使得L(R)=L(M)。
2.对于∑上的一个正规式R，可以构造一个∑上的NFAM，使的L(M)=L(R)。
大致想法：
第一步：
根据选择的词法类型，写出它的正则式。
无符号数的正则式为d*(.dd*|ε)(e(+|-|ε)dd*|ε)，这个比较容易。
第二步：
根据正则式构建与之等价的NFA。
第三步：
NFA转换为DFA。
由于出现+的地方可以出现“-”，出现“-”的地方可以出现“+”，所以可以将“+”与“-”等价。
状态集换名
确定有穷自动机的简化
有了上面的DFA，然后就是将自动机在计算机中构建。
好的数据结构能使编程事半功倍。我采用的是Trie图。
每个状态定义一个结构体：
structnode
{
intnumber;//对应状态下标
boolflag;//该状态是否是终态
node*Next[4];//分别代表吸收数字d、e、.、+或-的下一个状态指针
node()
{
memset(Next,NULL,sizeof(Next));
}
};
相互之间可以转移的状态连边，用指针模拟边。
共有4种边：
接受d由边Next[0]转移
接受e由边Next[1]转移
接受.由边Next[2]转移
接受+或-由边Next[3]转移
假设处理到operation中第i个字符（从0开始）
1.若operation[i]不是d,.,e,+|-，则不是正则式表示的无符号数,失败，直接退出。
2.若operation[i]不是d,+|-，根据Trie图转移到下一个结点
a.若当前结点为NULL而i!=Size，则不是正则式表示的无符号数，失败，退出。
b.否则，若i==size且p->flag!=true,则不是正则式表示的无符号数，失败，退出。
c.否则，若i==size且p->flag==true,则是正则式表示的无符号数，成功，退出。
d.否则继续读入一个字符转入1，循环处理。
三、调试分析
由于题目本身比较简单，调试过程中没有出现棘手的debug,须注意的是Trie图建立过程中指针的指向。
此外，算法的时间复杂度为O(n),空间复杂度也为O(n)，完全可以接受。
程序运行截图：
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; /*********************************************************** *A004 模拟DFA 编写一个程序，模拟最少状态的确定有限自动机，判断输入串能否识别。 **********************************************************/ struct node { int number; bool flag; node *Next[4];//分别代表吸收数字d、e、.、+或-的下一个状态指针 node() { memset(Next,sizeof(Next)); } }; node *Root; /********************************************************** *函数名：BulidDFA() *参数：无 *返回值：DFA的指针 *功能:建立正则式d*(.dd*|ε)(e(+|-|ε)dd*|ε)对应的DFA **********************************************************/ node* BulidDFA() { //0的 node *p0=new node; p0->number=0; p0->flag=false; p0->Next[0]=new node;//0的0指向1 //1的 node *p1; p1=p0->Next[0]; p1->number=1; p1->flag=true; p1->Next[0]=p1; //1的0指向1 p1->Next[1]=new node; //1的1指向3 p1->Next[2]=new node; //1的2指向2 //3的 node *p3; p3=p1->Next[1]; p3->flag=false; p3->number=3; p3->Next[0]=new node;//3的0指向6 p3->Next[3]=new node;//3的3指向5 //2的 node *p2; p2=p1->Next[2]; p2->flag=false; p2->number=2; p2->Next[0]=new node;//2的0指向4 //4的 node *p4; p4=p2->Next[0]; p4->flag=true; p4->number=4; p4->Next[0]=p4; p4->Next[1]=p3;//4的1指向3 //5的 node *p5; p5=p3->Next[3]; p5->flag=false; p5->number=5; p5->Next[0]=new node; p3->Next[0]=p5->Next[0]; //6的 node *p6; p6=p5->Next[0]; p6->flag=true; p6->number=6; p6->Next[0]=p6; return p0; } /********************************************************* *函数名：SimulateDFA *参数：一个，代表代识别串的引用 *返回值：能识别返回True，否则返回false *功能:判断当前字符串能否被识别 **********************************************************/ bool SimulateDFA(string &operation) { int size=operation.size(); node *p=Root; for(int i=0;i<size;i++) { if(p==NULL) { cout<<operation<<"用无符号数对应的DFA识别失败！"<<endl; return false; } if(operation[i]>='0'&&operation[i]<='9') { p=p->Next[0]; } else if(operation[i]=='e') { p=p->Next[1]; } else if(operation[i]=='.') { p=p->Next[2]; } else if(operation[i]=='+'||operation[i]=='-') { p=p->Next[3]; } else { cout<<operation<<"用无符号数对应的DFA识别失败！"<<endl; return false; } } if(p==NULL||!p->flag) { cout<<operation<<"用无符号数对应的DFA识别失败！"<<endl; return false; } else { cout<<operation<<"能用无符号数对应的DFA识别成功！"<<endl; return true; } } /********************************************************* *函数名：ShowDFA *参数：一个，代表代识别串的引用 *返回值：无 *功能:输出当前能识别字符串咋DFA中的状态转移 **********************************************************/ void ShowDFA(string &operation) { int size=operation.size(); node *p=Root; for(int i=0;i<size;i++) { if(operation[i]>='0'&&operation[i]<='9') { cout<<p->number<<"--'"<<operation[i]<<"'-->"<<p->Next[0]->number; p=p->Next[0]; } else if(operation[i]=='e') { cout<<p->number<<"--'"<<operation[i]<<"'-->"<<p->Next[1]->number; p=p->Next[1]; } else if(operation[i]=='.') { cout<<p->number<<"--'"<<operation[i]<<"'-->"<<p->Next[2]->number; p=p->Next[2]; } else if(operation[i]=='+'||operation[i]=='-') { cout<<p->number<<"--'"<<operation[i]<<"'-->"<<p->Next[3]->number; p=p->Next[3]; } if(i%2==0) cout<<" "; else cout<<endl; } } /********************************************************* *函数名： MyMenu *参数：无 *返回值：无 *功能:菜单函数 **********************************************************/ void MyMenu() { string operation; int choice; bool flag; while(true) { flag=true; do { if(!flag) { cout<<"您的选择有误，请重新输入[ ]\b\b"; } else { cout<<"======================================<<endl; cout<<" 1.输入新字符串"<<endl; cout<<" 2.退出"<<endl; cout<<"======================================<<endl; cout<<"请输入您的选择[ ]\b\b"; } cin>>choice; flag=false; }while(choice!=1&&choice!=2); if(choice==2) { cout<<"成功退出!"<<endl; exit(0); } else { cout<<"请输入您的待识别字符串："; cin>>operation; if(SimulateDFA(operation)) ShowDFA(operation); } cout<<endl; } } int main() { Root=BulidDFA(); MyMenu(); system("pause"); return 0; }
