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

精品文档课 程 名 称: 从正规文法构造有穷状态自动机年级/专业/班: 11级计算机类（二）班 姓 名: 徐勇兵 学 号： E01114278 从正规文法构造有穷状态自动机输入：任意的正规文法输出：相应的有穷状态自动机要求：识别有穷状态自动机是确定的还是非确定的，生成相应的五元组形式。说明：应检查输入的是否正规文法。实验截图：测试一：测试二：*测试三：import java.util.Vector;import javax.swing.JOptionPane;class Toolspublic Vector protection(Vector vs)Vector newvector=new Vector();for(int i=0;ivs.size();i+)newvector.add(vs.get(i);return newvector;public VectorVector doubleprotection(VectorVector vs)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 ireturn 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;/public Vector addElements(Vector vs,Vectortemp) /class toolsclass ElementsVector end=new Vector();/表示终结符Vector noend=new Vector();/表示非终结符VectorVector produce=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;/ifnoend.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 Vector getend()return end;public Vector getnoend()return noend;public VectorVector getproduce()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); produce.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); produce.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); produce.add(temp9);*/ / System.out.println(produce.size()=+produce.size();/*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; /for return true;/public boolean isRGPcontain(String s)public boolean IsNoENd(String s) String ss=+s.charAt(0); if(! Iscontainend(ss)/如果不含有终结符,则为非终结符 return true; return false; / public booleanpublic void show()System.out.print(终结符输出如下：);for(int i=0;iend.size();i+)System.out.print(String)end.get(i)+, );System.out.println( );System.out.print(非终结符输出如下：);for(int i=0;inoend.size();i+)System.out.print(String)noend.get(i)+, );System.out.println( );System.out.print(产生式输出如下：);for(int i=0;iproduce.size();i+)System.out.println( );Vector temp=(Vector)produce.get(i);System.out.print(String)temp.get(0)+-+(String)temp.get(1);System.out.println( );/class Elementspublic class Test Elements elements;Tools tools=new Tools();Vector end=new Vector();/表示终结符Vector noend=new Vector();/表示非终结符Vector inputTable=new Vector();/表示输入符号的集合 即又穷字母表Vector statusTable=new Vector();/状态表VectorVector produce=new VectorVector();/产生式VectorVector newproduce=new VectorVector();/转换函数String start=S;/初态String last=Z;/终态public void firststep()if(elements.Iscontainend(aA)=true)System.out.println(yes);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=+right.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();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)/return false;if(elements.IsNoENd(two)=false)/return false;return true; public void FA()/构造自动机 public void setstatusTable()/状态表for(int i=0;inoend.size();i+)statusTable.add(noend.get(i);statusTable.add(last); public void setinputTable()/状态表for(int i=0;iend.size();i+)inputTable.add(end.get(i);public void show()System.out.print(状态表输出如下：);for(int i=0;istatusTable.size();i+)System.out.print(String)statusTable.get(i)+, );System.out.println( );System.out.print(字母表输出如下：);for(int i=0;iinputTable.size();i+)System.out.print(String)inputTable.get(i)+, );System.out.println( );System.out.print(转换函数输出如下：);for(int i=0;inewproduce.size();i+)System.out.println( );Vector temp=(Vector)newproduce.get(i);System.out.print(String)temp.get(0)+ +(String)temp.get(1)+ +(String)temp.get(2);System.out.println( );System.out.println(初态是+start);System.out.println(终态是+last);public boolean judge()boolean flag=true;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);else/System.out.println(11);Vector temp2=new Vector();temp2.add(left);temp2.ad