用Java语言实现NFA到DFA的等价变换桂日培

《用Java语言实现NFA到DFA的等价变换桂日培》由会员分享，可在线阅读，更多相关《用Java语言实现NFA到DFA的等价变换桂日培（8页珍藏版）》请在装配图网上搜索。

1、用Java语言实现NFA到DFA的等价变换姓名：桂日培单位：湖北工业大学计算机学院02计算机1班学号：0212002123时间：2005年10月31日一、实验目的1、理解什么是NFA和什么是DFA；2、掌握NFA和DFA之间的等价变换；3、了解程序设计语言Java的语言机制。二、实验小组(按姓氏拼音排序)：陈超、桂日培三、术语解释1、DFA确定的有穷自动机(DFA)M是一五元组M=(Q,工，,qO,Z),其中：(1) Q是一有穷状态集；(2) 工是有穷输入字母表；(3) 是从QXEQ的映射函数，称为状态变迁函数，定义式(ql,a)=q2表示在q1状态下读入字母a后，转到状态q2；(4) qOW

2、Q是唯一的初态；(5) Z包含于Q是终态集。2、NFA如果(q1,a)的值不唯一，而是一个状态子集的话，那么这样的FA是不确定的，称为不确定的有穷自动机(NFA)。NFA和DFA定义的主要差别是它们的映射函数不一样，NFA的函数定义为：:QX工Tp其中：pW2Q，即P是Q的任意子集，2Q是Q的幕集。四、实验步骤与内容1、实验环境：操作系统：MicrosoftWindowsXP编译平台：BorlandJBuilder2006Enterprise2、步骤与内容：(1) 启动JBuilder,新建一个名为:NFA_To_DFA的工程，模板为默认类型(Defaultproject)。(2) 打开新建的

3、工程。(3) 在工程里添加一个名为NfaDemo的Java文件。(4) 打开NfaDemo文件，编辑源代码。(5) 按“Ctrl+F9”对源文件进行编译。（6）按“Ctrl+Shift+F9”对目标文件进行连接。（7）点击工具栏上的“RunRun“NfaDemo.java”usingdefaults”运行。运行情况如下（以程序设计语言编译方法大连理工大学出版社（第三版）29页2.6（3为例）：D:BorlandJBuilder2006jdk1.5binjavaw-classpathE:Java工程NFA_to_DFAclasses;D:BorlandJBuilder2006jdk1.5libd

4、t.jar;D:BorlandJBuilder2006jdk1.5libtools.jar;D:BorlandJBuilder2006jdk1.5libhtmlconverter.jar;D:BorlandJBuilder2006jdk1.5libjconsole.jar;D:BorlandJBuilder2006jdk1.5jrelibjavaws.jar;D:BorlandJBuilder2006jdk1.5jrelibextsunjce_provider.jar;D:BorlandJBuilder2006jdk1.5jrelibextlocaledata.jar;D:BorlandJBu

5、ilder2006jdk1.5jrelibextsunpkcs11.jar;D:BorlandJBuilder2006jdk1.5jrelibextdnsns.jar;D:BorlandJBuilder2006jdk1.5jrelibplugin.jar;D:BorlandJBuilder2006jdk1.5jrelibdeploy.jar;D:BorlandJBuilder2006jdk1.5jrelibimthaiim.jar;D:BorlandJBuilder2006jdk1.5jrelibimindicim.jar;D:BorlandJBuilder2006jdk1.5jrelibch

6、arsets.jar;D:BorlandJBuilder2006jdk1.5jrelibjsse.jar;D:BorlandJBuilder2006jdk1.5jrelibrt.jar;D:BorlandJBuilder2006jdk1.5jrelibjce.jarNfaDemo请输入NFA（Q,工，5,q,F）的情况：初态集q=1终态集（格式如：E#或EF#）F=5#请输入字母表（格式如：01#）工=01#请输入变迁函数中变迁次数：6请输入变换规则（格式如:A0B或AaB）:102#202#212#213#304#415#原来的NFA如下：初始状态：q=1终态集合：F=5字母表：工=0,1变

7、换规则如下：1- 0-22- 0-22-1-22-1-33- 0-44- 1-51（状态）laIb12222,32,32,42,32,422,3,52,3,52,42,3转换后的DFA如下：初始状态：q=A终态集合：F=E字母表：工=0,1变换规则如下：A-0-BB-0-BB-1-CC-0-DC-1-CD-0-BD-1-EE-0-DE-1-C五、实验总结通过本次实验，本人加深了对NFA和DFA概念的理解，掌握了NFA和DFA之间的等价变换,初步了解了Java语言的语言机制，学会了如何用JBuilder开发一个Java工程。在实验过程中将nfaDfa()中的判断新初态的部分进行了修正，去掉了原代

8、码中的“判断新初态”的代码段，在起所属的for语句上加入语句：“begin.add(a);”，程序在Jbuilder环境下运行成功。六、附源程序代码：/NfaDemo.javaimportjava.util.*;importjava.io.*;classNfaNodeNfaNode(Strings,Stringr,Stringn)start=s;rec=r;next=n;/NFA结点类，保存开始状态，接收字母，下一状态。publicStringretStart()returnstart;/返回开始状态publicStringretRec()returnrec;/返回接收的字母publicStr

9、ingretNext()returnnext;/返回一下状态publicStringtoString()/重载toString()，如A-0-B，表示A接收0后到达Breturnstart+-+rec+-+next;privateStringstart;privateStringrec;privateStringnext;classNfa/NFA类/al保存状态变化等信息，保存初态，e保存终态集Nfa(ArrayLista1,ArrayListb,ArrayListe,ArrayListc)convertSet=a1;begin=b;end=e;charList=c;voiddisplayO/

10、显示NFASystem.out.println(初始状态：q=+begin);System.out.println(终态集合：F=+end);System.out.println(字母表：工二+charList);System.out.println(变换规则如下6：)；Iteratorit=convertSet.iterator();while(it.hasNext()Objectelement=it.next();System.out.println(element);/用java中迭代子(iterator)来实现显示voidnfaToDfa()/核心部分方法nfaToDfa()将NFA转

11、化DFAArrayListi=newArrayList();i.add(begin);/begin加入i中ArrayListi0=newArrayList();/i0ArrayListi1=newArrayList();/i1for(intk=0;ki.size();k+)Objectob1=i.get(k);ArrayListitem=(ArrayList)ob1;ArrayListitem0=newArrayList();ArrayListitem1=newArrayList();for(intl=0;litem.size();l+)Objectstr1=item.get(l);Itera

12、torit2=convertSet.iterator();while(it2.hasNext()Objectob2=it2.next();NfaNodenode1=(NfaNode)ob2;StringstrS=node1.retStart();StringstrR=node1.retRec();StringstrN=node1.retNext();if(str1.equals(strS)&strR.equals(charList.get(0)&!item0.contains(strN)item0.add(strN);if(str1.equals(strS)&strR.equals(charL

13、ist.get(1)&!item1.contains(strN)item1.add(strN);if(itemO.size()=O)/若itemO为空，把加入item0.add();辻(item1.size()=0)/若iteml为空，把加入item1.add();10. add(itemO);11. add(item1);if(!i.contains(itemO)&!itemO.contains()i.add(itemO);if(!i.contains(item1)&!item1.contains()i.add(item1);System.out.println(n+I(状态)IaIb);/

14、打印表格for(intn=O;ni.size();n+)Objects1=i.get(n);Objects2=iO.get(n);Objects3=i1.get(n);System.out.println(s1+s2+s3);ArrayListbeginTemp=newArrayList(begin);ArrayListconvertSetTemp=newArrayList(convertSet);ArrayListendTemp=newArrayList(end);begin.clear();convertSet.clear();end.clear();/begin,endconvertSe

15、t清空begin.add(A);/初态固定为Afor(intj=0;ji.size();j+)Objectobx=i.get(j);ArrayListalx=(ArrayList)obx;Objectobx0=i0.get(j);ArrayListalx0=(ArrayList)obx0;Objectobx1=i1.get(j);ArrayListalx1=(ArrayList)obx1;IteratorendIt=endTemp.iterator();while(endlt.hasNext()/判断是否是新的终态集的元素，若是加入endObjectendItem=endIt.next();i

16、f(alx.contains(endItem)end.add(String.valueOf(char)(A+j);ArrayListalk=newArrayList();alk.add();if(!obx0.equals(alk)convertSet.add(newNfaNode(String.valueOf(char)(A+j),String.valueOf(charList.get(0),String.valueOf(char)(A+i.indexOf(obx0);if(!obx1.equals(alk)convertSet.add(newNfaNode(String.valueOf(ch

17、ar)(A+j),String.valueOf(charList.get(1),String.valueOf(char)(A+i.indexOf(obx1);privateprivateprivateprivateArrayListArrayListArrayListArrayListconvertSet;begin;end;charList;/分别保存状态变换的类集分别保存开始状态集分别保存终止状态集字母表publicclassNfaDemo/NFA测试publicstaticvoidmain(Stringargs)throwsIOExceptionchare;ArrayListbeginO

18、b二newArrayList();/beginOb保存初态ArrayListcharListOb=newArrayList();/charListOb保存字母表intconvertNum;/convertNum保变迁函数中变迁次数ArrayListendOb=newArrayList();/保存终态集ArrayListconvertOb=newArrayList();System.out.println(请输入NFA(Q,工，,q,F)的情况：)；/保存变迁BufferedReaderbr1=newBufferedReader(newInputStreamReader(System.in);S

19、ystem.out.print(初态集q=);beginOb.add(String.valueOf(char)br1.read();System.out.print(终态集(格式如：E#或EF#)F=);BufferedReaderbr2=newBufferedReader(newInputStreamReader(System.in);doe=(char)br2.read();/先把char类型转化为Sring类型endOb.add(String.valueOf(e);/e加入到终态集的类集中while(e!=#);endOb.remove(#);/删除#System.out.print(请

20、输入字母表(格式如：01#)工二)；BufferedReaderbr3=newBufferedReader(newInputStreamReader(System.in);charListOb.add(String.valueOf(char)br3.read();charListOb.add(String.valueOf(char)br3.read();System.out.print(请输入变迁函数中变迁次数：)；BufferedReaderbr4=newBufferedReader(newInputStreamReader(System.in);convertNum=Integer.par

21、seInt(br4.readLine();/把从键盘输入的String类型转化为int类型System.out.println(请输入变换规则8(格式如:A0B或AaB):);for(inti=0;iconvertNum;i+)Stringm,n,p;BufferedReaderbr5=newBufferedReader(newInputStreamReader(System.in);m=String.valueOf(char)br5.read();n=String.valueOf(char)br5.read();p=String.valueOf(char)br5.read();convertOb.add(newNfaNode(m,n,p);/把输入的转变等信息存入类集convertOb中Nfanfa1=newNfa(convertOb,beginOb,endOb,charListOb);System.out.println（n原来的NFA如下：）；nfal.displayO;/显示NFAnfal.nfaToDfa（）;/NF转为DFASystem.out.println（n转换后的DFA如下:）;nfal.displayO;/显示DFA