從正規(guī)文法構(gòu)造有窮狀態(tài)自動機

1、 特至I 學(xué)誠H 課程名稱：從正規(guī)文法構(gòu)造有夯狀態(tài)自動機 年級/專業(yè)/班:11級計算機類（二）班 姓名：徐勇兵 E01114278 從正規(guī)文法構(gòu)造有窮狀態(tài)自動機 輸入：任意的正規(guī)文法 輸由：相應(yīng)的有窮狀態(tài)自動機 要求：識別有窮狀態(tài)自動機是確定的還是 非確定的，生成相應(yīng)的五元組形式。 說明：應(yīng)檢查輸入的是否正規(guī)文法。 實驗截圖： 測試一：修結(jié)符輸出如下；如非終給荷輸出如下：5,5,A,B,A,B,產(chǎn)生式輸出如下：3 3- -akSakS- -hBShBS- -ee A A- -山-汕4B4B- -a5a5 EE是正規(guī)式狀態(tài)表輸出如下；*A,A,比“字母表輸出如下；工 6轉(zhuǎn)換函數(shù)輸出如下：3 3a

2、 aASUBSASUBSe eZkZkaBaBA AkABaSkABaSb btotoA AB*ZB*Z初態(tài)是S S終態(tài)是工是DFADFA 測試二： t terfninatea?lstLJavaAfpiicationjvrsrogrerfninatea?lstLJavaAfpiicationjvrsrograjwajwr ri iJsJs jav&jav& jrjr然結(jié)符輸出2 2口木：a,a,6 6 非終結(jié)符輸出如下；S,AS,Af fB,產(chǎn)生式輸出如下： 5 5- -alal S S- -bDbD3 3- -yeye k k- -bAbAB BaSaSB B- -ADADA

3、 AB B- -ytyt 方一AMAM乩4 4不是正規(guī)式程序結(jié)束 * 測試三： AaB B B- -?aS?aS E E- -bibi BeBe S S- -aBaB 是正規(guī)式 狀態(tài)表輸出如下:二，%B勺字母裝輸出如下：R,匕,轉(zhuǎn)換函數(shù)輸出如下 5 5日國 SEESEE S Se e2 2 AaEAaE 亞A A EaEaS S EbAEbA BeBe2 2 S Sa aS S 初態(tài)是S S： 終態(tài)是工 不是NF0NF0 importjava.util.Vector; importjavax.swing.JOptionPane; classTools publicVectorprotectio

4、n(Vectorvs) Vectornewvector=newVector(); for(inti=0;ivs.size();i+) newvector.add(vs.get(i); returnnewvector; doubleprotection(VectorVector vs)( VectorVectornewvector=newVectorVector(); for(inti=0;ivs.size();i+) Vectorproduce=(Vector)vs.get(i); Vectortemp=newVector(); for(intj=0;jproduce.size();j+) t

5、emp.add(String)produce.get(j); /forj newvector.add(temp); /fori returnnewvector; publicVectoraddElements(Vectorvs,Vectortemp) for(inti=0;itemp.size();i+) if(!vs.contains(temp.get(i) vs.add(temp.get(i); /for returnvs; /publicVectoraddElements(Vector vs,Vectortemp)/classtoolsclassElements Vectorend=ne

6、wVector();/表示終結(jié)符 Vectornoend=newVector();/表示非終結(jié)符 VectorVectorproduce=newVectorVector();/產(chǎn)生式 publicVectorVector publicvoidsetend()/終結(jié)符元素添加 while(true) Strings=JOptionPane.showInputDialog(null,請輸入終結(jié)符)； if(s=null)return;/ifend.add(s);/while/publicvoidaddend()/元素添加 publicvoidsetnoend()/非終結(jié)符元素添加 while(tr

7、ue) Strings=JOptionPane.showInputDialog(null,非請輸入終結(jié)符); if(s=null)return;/ifnoend.add(s); /while /publicvoidaddnoend()/ publicvoidsetproduce() while(true) Strings=JOptionPane.showInputDialog(null,請輸入產(chǎn)生式，-隔開); if(s=null) return; Vectortemp=newVector(); temp.add(s.split(-)0); temp.add(s.split(-)1); pro

8、duce.add(temp); /while /publicvoidaddproduce() publicVectorgetend() returnend; publicVectorgetnoend() returnnoend; publicVectorVectorgetproduce() duce; publicvoidrun() /*TEST*/ end.add(a); end.add(b); noend.add(S); noend.add(A); noend.add(B); Vectortemp=newVector(); temp.add(S); temp.a

9、dd(aA); produce.add(temp); /*/ Vectortemp1=newVector(); temp1.add(S); temp1.add(bB); produce.add(temp1); /*/ Vectortemp2=newVector(); temp2.add(S); temp2.add(e); produce.add(temp2); /*/ Vectortemp3=newVector(); temp3.add(A); temp3.add(aB); produce.add(temp3); /*/ Vectortemp4=newVector(); temp4.add(A

10、); temp4.add(bA); produce.add(temp4); /*/ Vectortemp5=newVector(); temp5.add(B); temp5.add(aS); produce.add(temp5); /*/ Vectortemp6=newVector(); temp6.add(B); temp6.add(bA); produce.add(temp6); /*/ Vectortemp7=newVector(); temp7.add(B); temp7.add(e); produce.add(temp7); /*/ Vectortemp8=newVector();

11、temp8.add(S); temp8.add(aB); produce.add(temp8); /*Vectortemp9=newVector(); temp9.add(S); temp9.add(aAA); produce.add(temp9);*/ /System.out.println(produce.size()=+produce.size(); /*TEST*/ /this.setend(); /this.setnoend(); /this.setproduce(); publicbooleanIscontainend(Strings)/正則表達(dá)式判斷s1是否在END的閉包里面 正

12、則忘了怎么寫了 intlength=s.length(); for(inti=0;ilength;i+) ( Stringa=+s.charAt(i); if(end.contains(a) continue; elsereturnfalse; /for returntrue; /publicbooleanisRGPcontain(Strings) publicbooleanIsNoENd(Strings) Stringss=+s.charAt(0); if(!Iscontainend(ss)/如果不含有終結(jié)符，則為非終結(jié)符 returntrue; returnfalse; /publicbo

13、olean publicvoidshow() System.out.print(終結(jié)符輸出如下：); for(inti=0;iend.size();i+) System.out.print(String)end.get(i)+,); System.out.println(); System.out.print(非終結(jié)符輸出如下：); for(inti=0;inoend.size();i+) System.out.print(String)noend.get(i)+,); System.out.println(); System.out.print(產(chǎn)生式輸出如下：); for(inti=0;i

14、produce.size();i+) System.out.println(); Vectortemp=(Vector)produce.get(i); System.out.print(String)temp.get(0)+-+(String)temp.get(1); System.out.println(); classElementspublicclassTest Elementselements; Toolstools=newTools(); Vectorend=newVector(); Vectornoend=newVector(); VectorinputTable=newVecto

15、r();/表示輸入符號的集合即又 窮字母表 VectorstatusTable=newVector();/狀態(tài)表 VectorVectorproduce=newVectorVector();/產(chǎn)生式 表示終結(jié)符 表示非終結(jié)符 VectorVectornewproduce=newVectorVector();/轉(zhuǎn)換 函數(shù) Stringstart=S;/初態(tài) Stringlast=Z;/終態(tài) publicvoidfirststep() if(elements.Iscontainend(aA)=true) System.out.println(yes); for(inti=0;iproduce.si

16、ze();i+) Vectortemp=produce.get(i); Stringleft=temp.get(0); Stringright=temp.get(1); if(right.length()!=1)/S-aA形式 Stringone=+right.charAt(0); Stringtwo=+right.charAt(1); Vectortemp1=newVector(); temp1.add(left); temp1.add(one); temp1.add(two); newproduce.add(templ); /if else/S-a形式 Stringone=+right.c

17、harAt(0); Vectortemp1=newVector(); temp1.add(left); temp1.add(one); temp1.add(last); newproduce.add(temp1); publicbooleaniszhenggui() for(inti=0;iproduce.size();i+) Vectortemp=produce.get(i); Stringleft=temp.get(0); Stringright=temp.get(1); if(right.length()2) returnfalse; if(right.length()=1) if(el

18、ements.IsNoENd(right)=false)/S-A不滿足 returnfalse; if(right.length()=2) Stringone=+right.charAt(0); Stringtwo=+right.charAt(1); if(elements.Iscontainend(one)=false) returnfalse; if(elements.IsNoENd(two)=false) returnfalse; ) ) returntrue; ) publicvoidFA()構(gòu)造自動機 ) publicvoidsetstatusTable()/狀態(tài)表 for(inti

19、=0;inoend.size();i+) statusTable.add(noend.get(i); )statusTable.add(last); publicvoidsetinputTable()/狀態(tài)表 for(inti=0;iend.size();i+) inputTable.add(end.get(i); publicvoidshow() System.out.print(狀態(tài)表輸出如下：); for(inti=0;istatusTable.size();i+) System.out.print(String)statusTable.get(i)+,); System.out.pri

20、ntln(); System.out.print(字母表輸出如下：); for(inti=0;iinputTable.size();i+) System.out.print(String)inputTable.get(i)+,); System.out.println(); System.out.print(轉(zhuǎn)換函數(shù)輸出如下：); for(inti=0;inewproduce.size();i+) System.out.println(); Vectortemp=(Vector)newproduce.get(i); System.out.print(String)temp.get(0)+(St

21、ring)temp.get(1)+ +(String)temp.get(2); System.out.println(); System.out.println(初態(tài)是+start); System.out.println(終態(tài)是+last); ) publicbooleanjudge() booleanflag=true; VectorVectorvs=newVectorVector(); /Vectorvv=newVector(); for(inti=0;inewproduce.size();i+) Vectortemp=newproduce.get(i); Stringleft=temp.get(0); Stringmidle=temp.get(1); if(vs.isEmpty()如果是第一次放入數(shù)據(jù) Vectortemp2=newVector(); temp2.add(left); temp2.add(midle);