用Java语言实现NFA到DFA的等价变换
姓名：桂日培
单位：湖北工业大学计算机学院02计算机1班 学号：0212002123
时间：2005年10月31日
一、实验目的
1、理解什么是NFA和什么是DFA； 2、掌握NFA和DFA之间的等价变换； 3、了解程序设计语言Java的语言机制。 二、实验小组（按姓氏拼音排序）：陈超、桂日培 三、术语解释 1、DFA
确定的有穷自动机（DFA）M是一五元组
M=(Q,∑,δ,q0,Z),
其中：
（1） Q是一有穷状态集； （2） ∑是有穷输入字母表；
（3） δ是从Q×∑?Q的映射函数，称为状态变迁函数，定义式δ(q1,a)=q2表示在q1
状态下读入字母a后，转到状态q2；
（4） q0∈Q是唯一的初态； （5） Z包含于Q是终态集。 2、NFA
如果δ(q1,a)的值不唯一，而是一个状态子集的话，那么这样的FA是不确定的，称为不确定的有穷自动机（NFA）。NFA和DFA定义的主要差别是它们的映射函数不一样，NFA的δ函数定义为：
δ:Q×∑?ρ
其中：ρ∈2Q,即ρ是Q的任意子集，2Q是Q的幂集。 四、实验步骤与内容 1、实验环境：
操作系统：Microsoft Windows XP
编译平台：Borland JBuilder 2006 Enterprise 2、步骤与内容： （1）启动JBuilder，新建一个名为：NFA_To_DFA的工程，模板为默认类型（Default project）。 （2）打开新建的工程。
（3）在工程里添加一个名为NfaDemo的Java文件。 （4）打开NfaDemo文件，编辑源代码。 （5）按“Ctrl+F9”对源文件进行编译。
（6）按“Ctrl+Shift+F9”对目标文件进行连接。
（7）点击工具栏上的“Run?Run “NfaDemo.java” using defaults”运行。
运行情况如下（以《程序设计语言编译方法》大连理工大学出版社（第三版）29页2.6(3为例)）：
D:\\Borland\\JBuilder2006\\jdk1.5\\bin\\javaw -classpath \工程
\\NFA_to_DFA\\classes;D:\\Borland\\JBuilder2006\\jdk1.5\\lib\\dt.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\lib\\tools.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\lib\\htmlconverter.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\lib\\jconsole.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\javaws.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\ext\\sunjce_provider.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\ext\\localedata.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\ext\\sunpkcs11.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\ext\\dnsns.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\plugin.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\deploy.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\im\\thaiim.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\im\\indicim.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\charsets.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\jsse.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\rt.jar;D:\\Borland\\JBuilder2006\\jdk1.5\\jre\\lib\\jce.jar\请输入 NFA(Q,Σ,δ,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] 变换规则如下δ： 1-0->2 2-0->2 2-1->2 2-1->3 3-0->4 4-1->5
I(状态) Ia Ib [1] [2] [@] [2] [2] [2, 3]
[2, 3] [2, 4] [2, 3] [2, 4] [2] [2, 3, 5] [2, 3, 5] [2, 4] [2, 3]
转换后的DFA如下: 初始状态：q=[A] 终态集合：F=[E] 字母表:Σ=[0, 1] 变换规则如下δ： A-0->B B-0->B B-1->C C-0->D C-1->C D-0->B D-1->E E-0->D E-1->C
五、实验总结 通过本次实验，本人加深了对NFA和DFA概念的理解，掌握了NFA和DFA之间的等价变换，初步了解了Java语言的语言机制，学会了如何用JBuilder开发一个Java工程。在实验过程中将 nfaDfa()中的判断新初态的部分进行了修正，去掉了原代码中的“判断新初态”的代码段，在起所属的for语句上加入语句：“begin.add(‘a’);”，程序在Jbuilder环境下运行成功。
六、附源程序代码： //NfaDemo.java
import java.util.*; import java.io.*; class NfaNode {
NfaNode(String s,String r,String n) {
start=s; rec=r; next=n;
} //NFA结点类，保存开始状态，接收字母，下一状态。 public String retStart() {
return start; // 返回开始状态 }
public String retRec() {
return rec; // 返回接收的字母 }
public String retNext() {
return next; // 返回一下状态 }
public String toString() // 重载toString()，如A-0->B，表示A接收0后到达B {
return start+\ }
private String start; private String rec; private String next; }
class Nfa // NFA类 {
// al保存状态变化等信息，保存初态，e保存终态集
Nfa(ArrayList a1, ArrayList b, ArrayList e, ArrayList c) {
convertSet=a1; begin=b; end=e;
charList=c; }
void display() // 显示NFA {
System.out.println(\初始状态：q=\ System.out.println(\终态集合：F=\ System.out.println(\字母表:Σ=\ System.out.println(\变换规则如下δ：\ Iterator it =convertSet.iterator(); while(it.hasNext()) {
Object element=it.next(); System.out.println(element);
} // 用java中迭代子（iterator）来实现显示 }
void nfaToDfa() // 核心部分方法nfaToDfa()将NFA转化DFA {
ArrayList i=new ArrayList();
i.add(begin); // begin加入i中
ArrayList i0=new ArrayList(); // i0 ArrayList i1=new ArrayList(); // i1 for(int k=0;k Object ob1=i.get(k); ArrayList item=( ArrayList)ob1; ArrayList item0=new ArrayList(); ArrayList item1=new ArrayList(); for (int l=0;l Object str1=item.get(l); Iterator it2=convertSet.iterator(); while(it2.hasNext()) { Object ob2=it2.next(); NfaNode node1=(NfaNode)ob2; String strS=node1.retStart(); String strR=node1.retRec(); String strN=node1.retNext(); if(str1.equals(strS)&&strR.equals(charList.get(0))&&!item0.contains(strN)) item0.add(strN); if(str1.equals(strS)&&strR.equals(charList.get(1))&&!item1.contains(strN)) item1.add(strN); } } if(item0.size()==0) // 若item0为空，把@加入 item0.add(\ if(item1.size()==0) // 若item1为空，把@加入 item1.add(\ i0.add(item0); i1.add(item1); if(!i.contains(item0)&&!item0.contains(\ i.add(item0); if(!i.contains(item1)&&!item1.contains(\ i.add(item1); } System.out.println(\状态) Ia Ib\打印表格 for(int n=0;n Object s1=i.get(n); Object s2=i0.get(n); Object s3=i1.get(n); System.out.println(s1+\ } ArrayList beginTemp=new ArrayList(begin); ArrayList convertSetTemp=new ArrayList(convertSet); ArrayList endTemp=new ArrayList(end); begin.clear(); convertSet.clear();