《从正则文法构造有穷状态自动机.docx》由会员分享,可在线阅读,更多相关《从正则文法构造有穷状态自动机.docx(4页珍藏版)》请在金锄头文库上搜索。
1、#include using namespace std;const int maxsize=10;class DFA /定义 DFA类 private: int Mmaxsizemaxsize; /定义整形数组 char Vnmaxsize,Vtmaxsize; /分别用数组装终结符号与非终结符号 int VnNum,VtNum; /定义两个整形变量分别存放终结符号与非终结符号的个数 public: DFA(); /构造函数 DFA() /析出函数 void print(); /输出函数 int move(char start,char s); /判断字符函数;int DFA:move(ch
2、ar start,char s) char t10; char next=start; int left=0,right=0,i=0,j=0; while(si!=0) ti=si+; ti=0; while(t0!=0) left=0;right=0; while(next!=Vnleft) left+; while(t0!=Vtright) right+; if(Mleftright!=-1&leftVnNum&rightVtNum) next=VnMleftright; coutM(Vnleft,Vtright)=nextendl; else return 0; i=1; while(t
3、i!=0)ti-1=ti+; ti-1=0; return 1; DFA:DFA() char grammarmaxsize,nmaxsize,tmaxsize; int rule,left,right,final; int i=0,j=0,k=0; coutrule; coutn; coutt; coutgrammar; Vn0=S; j=0; while(nj!=0) Vnj+1=nj+; VnNum=j+1; while(ti!=0) Vti=ti+; VtNum=i; for(i=0;iVnNum;i+) for(j=0;jgrammar; while(Vnk!=grammar0) k
4、+; final=k; while(grammarj!=0) j+; if(j=5) k=0; while(Vtk!=grammar4)k+; left=0; right=k; else k=0; while(Vnk!=grammar4) k+; left=k; k=0; while(Vtk!=grammar5) k+; right=k; Mleftright=final; i+; void DFA:print() /打印五元组 int i=0,j=0; coutDFA (; while(i!=VnNum) coutVni+,; cout,; while(j!=VtNum) coutVtj+,
5、; cout,Mendl; coutendl; i=0; while(i!=VnNum) j=0; while(j!=VtNum) if(Mij!=-1) coutM(Vni; cout,Vtj)=VnMijendl; j+; i+; cout,Vn0,Vn1;int main() char t10; /定义字符型数组 int i; /定义变量i cout-endl; couti; /输入 DFA s; while(i=3) /判断输入数字 if(i=2)s.print(); /如果是2,打印 if(i=3) coutt;if(s.move(S,t)cout字符串t可以被该DFA所接收; else cout字符串t不能被该DFA所接收; couti; system(pause);