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

用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();

end.clear(); // begin，end convertSet清空 begin.add('A'); // 初态固定为A for(int j=0;j

Object obx=i.get(j);

ArrayList alx=(ArrayList)obx; Object obx0=i0.get(j);

ArrayList alx0=(ArrayList)obx0; Object obx1=i1.get(j);

ArrayList alx1=(ArrayList)obx1; Iterator endIt=endTemp.iterator();

while(endIt.hasNext()) // 判断是否是新的终态集的元素，若是加入end {

Object endItem=endIt.next(); if(alx.contains(endItem))

end.add(String.valueOf((char)('A'+j))); }

ArrayList alk=new ArrayList(); alk.add(\

if(!obx0.equals(alk)) {

convertSet.add(new

NfaNode(String.valueOf((char)('A'+j)),String.valueOf(charList.get(0)),String.valueOf((char)('A'+i.indexOf(obx0))))); }

if(!obx1.equals(alk)) {

convertSet.add(new

NfaNode(String.valueOf((char)('A'+j)),String.valueOf(charList.get(1)),String.valueOf((char)('A'+i.indexOf(obx1))))); } } }

private ArrayList convertSet; // 分别保存状态变换的类集 private ArrayList begin; // 分别保存开始状态集 private ArrayList end; // 分别保存终止状态集 private ArrayList charList; // 字母表 }

public class NfaDemo // NFA测试 {

public static void main(String args[]) throws IOException

{

char e;

ArrayList beginOb=new ArrayList(); // beginOb保存初态

ArrayList charListOb=new ArrayList(); // charListOb保存字母表 int convertNum; // convertNum保变迁函数中变迁次数 ArrayList endOb=new ArrayList(); // 保存终态集 ArrayList convertOb=new ArrayList();

System.out.println(\请输入 NFA(Q,Σ,δ,q,F)的情况:\保存变迁 BufferedReader br1= new BufferedReader(new InputStreamReader(System.in)); System.out.print(\初态集q=\

beginOb.add(String.valueOf((char)br1.read())); System.out.print(\终态集(格式如：E#或EF#)F=\ BufferedReader br2= new BufferedReader(new InputStreamReader(System.in)); do {

e=(char)br2.read(); // 先把char类型转化为Sring类型 endOb.add(String.valueOf(e)); // e加入到终态集的类集中 }while(e!='#');

endOb.remove(\删除#

System.out.print(\请输入字母表(格式如：01#)Σ=\ BufferedReader br3= new BufferedReader(new InputStreamReader(System.in)); charListOb.add(String.valueOf((char)br3.read())); charListOb.add(String.valueOf((char)br3.read())); System.out.print(\请输入变迁函数中变迁次数:\ BufferedReader br4= new BufferedReader(new InputStreamReader(System.in)); convertNum=Integer.parseInt(br4.readLine()); // 把从键盘输入的String类型转化为int类型

System.out.println(\请输入变换规则δ(格式如:A0B或AaB)：\for(int i=0;i

String m,n,p; BufferedReader br5=new BufferedReader(new InputStreamReader(System.in));

m=String.valueOf((char)br5.read()); n=String.valueOf((char)br5.read()); p=String.valueOf((char)br5.read()); convertOb.add(new NfaNode(m,n,p));

} // 把输入的转变等信息存入类集convertOb中

Nfa nfa1=new Nfa(convertOb,beginOb,endOb,charListOb); System.out.println(\原来的NFA如下:\ nfa1.display(); // 显示NFA nfa1.nfaToDfa(); // NF转为DFA

System.out.println(\转换后的DFA如下:\ nfa1.display(); // 显示DFA

} }

本文来源：https://www.bwwdw.com/article/04lg.html