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

1、课 程 名 称: 从正规文法构造有穷状态自动机年级/专业/班: 11级计算机类（二）班 姓 名: 徐勇兵 学 号： E01114278 从正规文法构造有穷状态自动机输入：任意的正规文法输出：相应的有穷状态自动机要求：识别有穷状态自动机是确定的还是非确定的，生成相应的五元组形式。说明：应检查输入的是否正规文法。实验截图：测试一：测试二：*测试三：import java.util.Vector;import javax.swing.JOptionPane;class Toolspublic Vector<String> protection(Vector<String> v

2、s)Vector<String> newvector=new Vector<String>();for(int i=0;i<vs.size();i+)newvector.add(vs.get(i);return newvector;public Vector<Vector<String>> doubleprotection(Vector<Vector<String>> vs)Vector<Vector<String>> newvector=new Vector<Vector<Str

3、ing>>();for(int i=0;i<vs.size();i+)Vector<String> produce=(Vector<String>)vs.get(i);Vector<String> temp=new Vector<String>();for(int j=0;j<produce.size();j+)temp.add(String)produce.get(j);/for jnewvector.add(temp);/for ireturn newvector;public Vector<String>

4、 addElements(Vector<String> vs,Vector<String>temp)for(int i=0;i<temp.size();i+)/if(!vs.contains(temp.get(i) vs.add(temp.get(i); /forreturn vs;/public Vector<String> addElements(Vector<String> vs,Vector<String>temp) /class toolsclass ElementsVector<String> end=n

5、ew Vector<String>();/表示终结符Vector<String> noend=new Vector<String>();/表示非终结符Vector<Vector<String>> produce=new Vector<Vector<String>>();/产生式public void setend()/终结符元素添加while(true)String s=JOptionPane.showInputDialog(null,"请输入终结符");if(s=null)return;/

6、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,"请输

7、入产生式，->隔开"); if(s=null)return; Vector<String> temp=new Vector<String>(); temp.add(s.split("->")0); temp.add(s.split("->")1); produce.add(temp); /while/public void addproduce()public Vector<String> getend()return end;public Vector<String> getn

8、oend()return noend;public Vector<Vector<String>> getproduce()return duce;public void run() /*TEST*/end.add("a");end.add("b");noend.add("S");noend.add("A");noend.add("B"); Vector<String> temp=new Vector<String>(); temp.

9、add("S"); temp.add("aA"); produce.add(temp); /*/ Vector<String> temp1=new Vector<String>(); temp1.add("S"); temp1.add("bB"); produce.add(temp1); /*/ Vector<String> temp2=new Vector<String>(); temp2.add("S"); temp2.add("e&

10、quot;); produce.add(temp2); /*/ Vector<String> temp3=new Vector<String>(); temp3.add("A"); temp3.add("aB"); produce.add(temp3); /*/ Vector<String> temp4=new Vector<String>(); temp4.add("A"); temp4.add("bA"); produce.add(temp4); /*/ Vect

11、or<String> temp5=new Vector<String>(); temp5.add("B"); temp5.add("aS"); produce.add(temp5); /*/ Vector<String> temp6=new Vector<String>(); temp6.add("B"); temp6.add("bA"); produce.add(temp6); /*/ Vector<String> temp7=new Vector<

12、;String>(); temp7.add("B"); temp7.add("e"); produce.add(temp7); /*/ Vector<String> temp8=new Vector<String>(); temp8.add("S"); temp8.add("aB"); produce.add(temp8); /* Vector<String> temp9=new Vector<String>(); temp9.add("S"

13、); 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;i<length;i+) String

14、 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()

15、System.out.print("终结符输出如下：");for(int i=0;i<end.size();i+)System.out.print(String)end.get(i)+", ");System.out.println(" ");System.out.print("非终结符输出如下：");for(int i=0;i<noend.size();i+)System.out.print(String)noend.get(i)+", ");System.out.println(

16、" ");System.out.print("产生式输出如下：");for(int i=0;i<produce.size();i+)System.out.println(" ");Vector<String> temp=(Vector<String>)produce.get(i);System.out.print(String)temp.get(0)+"->"+(String)temp.get(1);System.out.println(" ");/class

17、 Elementspublic class Test Elements elements;Tools tools=new Tools();Vector<String> end=new Vector<String>();/表示终结符Vector<String> noend=new Vector<String>();/表示非终结符Vector<String> inputTable=new Vector<String>();/表示输入符号的集合 即又穷字母表Vector<String> statusTable=new

18、 Vector<String>();/状态表Vector<Vector<String>> produce=new Vector<Vector<String>>();/产生式Vector<Vector<String>> newproduce=new Vector<Vector<String>>();/转换函数String start="S"/初态String last="Z"/终态public void firststep()if(elements.

19、Iscontainend("aA")=true)System.out.println("yes");for(int i=0;i<produce.size();i+)Vector<String> 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.cha

20、rAt(1);Vector<String> temp1=new Vector<String>();temp1.add(left);temp1.add(one);temp1.add(two);newproduce.add(temp1);/ifelse/S->a形式String one=""+right.charAt(0);Vector<String> temp1=new Vector<String>();temp1.add(left);temp1.add(one);temp1.add(last);newproduce.ad

21、d(temp1);public boolean iszhenggui()for(int i=0;i<produce.size();i+)Vector<String> 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)Strin

22、g 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;i<noend.size();i+)statusTable.add(noend.get(i);

23、statusTable.add(last); public void setinputTable()/状态表for(int i=0;i<end.size();i+)inputTable.add(end.get(i);public void show()System.out.print("状态表输出如下：");for(int i=0;i<statusTable.size();i+)System.out.print(String)statusTable.get(i)+", ");System.out.println(" ");

24、System.out.print("字母表输出如下：");for(int i=0;i<inputTable.size();i+)System.out.print(String)inputTable.get(i)+", ");System.out.println(" ");System.out.print("转换函数输出如下：");for(int i=0;i<newproduce.size();i+)System.out.println(" ");Vector<String>

25、; temp=(Vector<String>)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 fl

26、ag=true;Vector<Vector<String>> vs=new Vector<Vector<String>>();/Vector<String> vv=new Vector<String>();for(int i=0;i<newproduce.size();i+)Vector<String> temp=newproduce.get(i);String left=temp.get(0);String midle=temp.get(1);if(vs.isEmpty()/如果是第一次放入数据Vector<String> temp2=new V