从正规文法构造有穷状态自动机

1、,.课 程 名 称: 从正规文法构造有穷状态自动机年级 / 专业 / 班:11 级计算机类（二）班姓名:徐勇兵学号：E01114278,.从正规文法构造有穷状态自动机输入： 任意的正规文法输出： 相应的有穷状态自动机要求： 识别有穷状态自动机是确定的还是非确定的，生成相应的五元组形式。说明： 应检查输入的是否正规文法。实验截图：测试一：,.测试二：*,.*测试三：class Toolspublic Vector protection(Vector vs)Vector newvector=new Vector();for(int i=0;ivs.size();i+)newvector.add(v

2、s.get(i);return newvector;,.publicVectorVectordoubleprotection(VectorVectorvs)VectorVector newvector=new VectorVector();for(int i=0;ivs.size();i+)Vector produce=(Vector)vs.get(i);Vector temp=new Vector();for(int j=0;jproduce.size();j+)temp.add(String)produce.get(j);/for jnewvector.add(temp);/for ire

3、turn newvector;public Vector addElements(Vector vs,Vectortemp)for(int i=0;itemp.size();i+)/if(!vs.contains(temp.get(i)vs.add(temp.get(i);/forreturn vs;/publicVectoraddElements(Vectorvs,Vectortemp)/class tools,.classElementsVector end=new Vector();/表示终结符Vector noend=new Vector();/表示非终结符VectorVector p

4、roduce=new VectorVector();/产生式public void setend()/终结符元素添加while(true)String s=JOptionPane.showInputDialog(null,请输入终结符 );if(s=null)return;/ifend.add(s);/while/public void addend()/元素添加public void setnoend()/非终结符元素添加while(true)String s=JOptionPane.showInputDialog(null,非请输入终结符);if(s=null)return;/ifnoen

5、d.add(s);,./while/public void addnoend()/public void setproduce()while(true)String s=JOptionPane.showInputDialog(null,if(s=null)return;Vector temp=new Vector();temp.add(s.split(-)0);temp.add(s.split(-)1);produce.add(temp);/while/public void addproduce()public Vectorgetend()return end;请输入产生式，-隔开 );pu

6、blic Vectorreturn noend;getnoend()public VectorVectorgetproduce()return duce;,.public void run()/*TEST*/end.add(a);end.add(b);noend.add(S);noend.add(A);noend.add(B);Vector temp=new Vector();temp.add(S);temp.add(aA);produce.add(temp);/*/Vector temp1=new Vector();temp1.add(S);temp1.add(bB);pro

7、duce.add(temp1);/*/Vector temp2=new Vector();temp2.add(S);temp2.add(e);produce.add(temp2);,./*/Vector temp3=new Vector();temp3.add(A);temp3.add(aB);produce.add(temp3);/*/Vector temp4=new Vector();temp4.add(A);temp4.add(bA);produce.add(temp4);/*/Vector temp5=new Vector();temp5.add(B);temp5.add(aS);pr

8、oduce.add(temp5);/*/Vector temp6=new Vector();temp6.add(B);temp6.add(bA);produce.add(temp6);/*/Vector temp7=new Vector();,.temp7.add(B);temp7.add(e);produce.add(temp7);/*/Vector temp8=new Vector();temp8.add(S);temp8.add(aB);produce.add(temp8);/*Vector temp9=new Vector();temp9.add(S);temp9.add(aAA);p

9、roduce.add(temp9);*/*TEST*/this.setend();/this.setnoend();/this.setproduce();public boolean Iscontainend(String s)/正则表达式判断s1 是否在 END 的闭包里面正则忘了怎么写了,.int length=s.length();for(int i=0;ilength;i+)String a=+s.charAt(i);if(end.contains(a)continue;else return false;/forreturn true;/public boolean isRGPcon

10、tain(String s)public boolean IsNoENd(String s)String ss=+s.charAt(0);if(! Iscontainend(ss)/如果不含有终结符,则为非终结符return true;return false;/public booleanpublic void show()终结符输出如下：);for(int i=0;iend.size();i+),.非终结符输出如下：);for(int i=0;inoend.size();i+)产生式输出如下：);for(int i=0;iproduce.size();i+)Vector temp=(Vec

11、tor)produce.get(i);/class Elementspublic class Test Elements elements;Tools tools=new Tools();Vector end=new Vector();/表示终结符Vector noend=new Vector();/表示非终结符,.VectorinputT able=newVector();/表示输入符号的集合即又穷字母表Vector statusTable=new Vector();/状态表VectorVector produce=new VectorVector();/产生式VectorVectornew

12、produce=newVectorVector();/转换函数String start=S;/初态String last=Z;/终态public void firststep()if(elements.Iscontainend(aA)=true)for(int i=0;iproduce.size();i+)Vector temp=produce.get(i);String left=temp.get(0);String right=temp.get(1);if(right.length()!=1)/S-aA形式String one=+right.charAt(0);String two=+ri

13、ght.charAt(1);Vector temp1=new Vector();temp1.add(left);temp1.add(one);temp1.add(two);,.newproduce.add(temp1);/ifelse/S-a形式String one=+right.charAt(0);Vector temp1=new Vector();temp1.add(left);temp1.add(one);temp1.add(last);newproduce.add(temp1);public boolean iszhenggui()for(int i=0;iproduce.size()

14、;i+)Vector temp=produce.get(i);String left=temp.get(0);String right=temp.get(1);if(right.length()2)return false;if(right.length()=1)if(elements.IsNoENd(right)=false)/S-A不满足return false;,.if(right.length()=2)String one=+right.charAt(0);String two=+right.charAt(1);if(elements.Iscontainend(one)=false)/

15、return false;if(elements.IsNoENd(two)=false)/return false;return true;public void FA()/构造自动机public void setstatusTable()/状态表for(int i=0;inoend.size();i+)statusT able.add(noend.get(i);statusT able.add(last);,.public void setinputTable()/状态表for(int i=0;iend.size();i+)inputTable.add(end.get(i);public v

16、oid show()状态表输出如下：);for(int i=0;istatusTable.size();i+)able.get(i)+, );字母表输出如下：);for(int i=0;iinputTable.size();i+)转换函数输出如下：);for(int i=0;inewproduce.size();i+)Vector temp=(Vector)newproduce.get(i);+(String)temp.get(1)+(String)temp.get(2);,.初态是 +start);终态是 +last);public boolean judge()boolean flag=t

17、rue;VectorVector vs=new VectorVector();/Vector vv=new Vector();for(int i=0;inewproduce.size();i+)Vector temp=newproduce.get(i);String left=temp.get(0);String midle=temp.get(1);if(vs.isEmpty()/如果是第一次放入数据Vector temp2=new Vector();temp2.add(left);temp2.add(midle);vs.add(temp2);elseVector temp2=new Vector();,.temp2.add(left);temp2.add(midle);midle=+midle);if(vs.contains(temp2)return false;elsevs.add(temp2);return true;public T est()elements=new Elements();elements.run();this.end=elements.getend();this.noend=elements.getnoend();this