NFA转换成DFA——编译原理

程序实现了从NFA转化成DFA的功能，输入输出都以状态转换表的形式，读取写入文件。代码比较简单，是编译原理课程的算法实现之一。

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.linkedHashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

import javax.swing.JOptionPane;


/**
 * 实现NFA到DFA的转换
 * 算法：子集法
 * 其中NFA的状态集使用Set存储
 * 具体使用linkedHashSet而不是HashSet，
 * 因为linkedHashSet元素取出数据和插入数据一致，
 * 可保证程序结果和手算结果相同
 * （虽然HashSet的结果等价，但有些需要新的对应关系）
 * 
 * 输入输出均为状态矩阵
 * 输入NFA状态矩阵stateOfNFA的格式为：
 * Q\E a b e_null
 * 1 45 s_null 2
 * 2 s_null 3 s_null
 * 3 s_null s_null 8
 * 4 s_null s_null 7
 * 5 s_null s_null 6
 * 6* s_null 9 2
 * 7* s_null 9 s_null
 * 8 9 s_null s_null
 * 9* s_null s_null s_null
 * 其中‘e_null‘表示空串e‘s_null‘表示空集
 * 第一行表示字母表中的字母，第一列表示状态集中的状态（不是集合）
 * 此NFA在书P37
 * 
 * NFA确定化过程构造的状态表stateN2D的格式为：
 * I			Ia			Ib
 * 12			54672	38
 * 54672*	s_null		398
 * 38*		9			s_null
 * 398		9			s_null
 * 9*			s_null		s_null
 * 其中‘s_null‘表示空集
 * 第一行表示Ia为I的e闭包的a弧e闭包...，第一列表示新的状态集
 * 写入文件时s_null表示为[]
 * @author Blue_Fat
 *
 */
public class NFA2DFA {
	private final int MAX = 100;//最多有100*100的状态矩阵
	private State[][] stateOfNFA = new State[MAX][MAX];//需要在构造方法里new分配内存
	private String[][] stateOfDFA = new String[MAX][MAX];
	private State[][] stateN2D = new State[MAX][MAX];//NFA确定化过程构造的状态表
	private int row col;//行列计数
	private int realRow realCol;//实际输入的行列数
	
	NFA2DFA（）{
		for（int i = 0; i			for（int j = 0; j				stateOfNFA[i][j] = new State（）;
				stateN2D[i][j] = new State（）;
				stateOfDFA[i][j] = new String（）;
			}
		}
	}
	private class State{	
		/*由于不能定义泛型数组，即不能有Set[]的定义形式，故用一个简单的类State来表示NFA的
		 * 状态，从而达到Set[]的类似目的
		 */
		Set state = new linkedHashSet（）;
	}
	private Set eee_Closure（Set eSta）{//e闭包，并解决eee...e=e的情况
		Set e_cls = new linkedHashSet（）;//一次e闭包状态集
		Set e_cls2nd = new linkedHashSet（）;//两次e闭包状态集
//		int count = 1;//计数
		e_cls = e_Closure（eSta）;
		e_cls2nd = e_Closure（e_cls）;//通过递归调用，解决eee...e=e这样重复多次e的情况
		while（!e_cls2nd.equals（e_cls））{//不相等时继续向下求e闭包
//			System.out.println（“count = “ + ++count）;
			e_cls = e_Closure（e_cls2nd）;
			e_cls2nd = e_Closure（e_cls）;
		}
		return e_cls2nd;
//		if（e_cls2nd.equals（e_cls））{
//			return e_cls;
//		} else {
//			return e_cls2nd;
//		}
	}
	private Set e_Closure（Set eSta）{//e闭包输入为一个状态集，输出为一个状态集
//		System.out.println（“eSta = “ + eSta）;
		Set e_cls = new linkedHashSet（）;//一次e闭包状态集
		Set fqeSet = new linkedHashSet（）;//f（qe）结果的集合
		int i j;//记录f（qe）结果在NFA状态表中的行列数
		int row col;//遍历NFA状态表的指针
		Iterator it = eSta.iterator（）;
		while（it.hasNext（））{
			String q = it.next（）;
//			System.out.println（“q = “ + q）;
			if（eSta.contains（q））{//若q∈I，则q∈e_closure（I）;
				e_cls.add（q）;
			//--------------寻找f（qe）----------------
				i = 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2015-04-24 08:33  NFA2DFA\
     文件         232  2015-03-25 17:56  NFA2DFA\.classpath
     文件         383  2015-03-25 17:56  NFA2DFA\.project
     文件          99  2015-04-24 09:28  NFA2DFA\GeneDFA.txt
     文件         424  2015-04-24 09:28  NFA2DFA\MiddleN2D.txt
     文件         393  2015-04-24 09:28  NFA2DFA\NFA.txt
     文件         185  2015-03-28 16:03  NFA2DFA\NFA_past.txt
     文件        6847  2015-03-28 22:41  NFA2DFA\NFA确定化算法.jar
     目录           0  2015-04-24 08:27  NFA2DFA\bin\
     文件         612  2015-04-24 08:48  NFA2DFA\bin\NFA2DFA$State.class
     文件        8976  2015-04-24 08:48  NFA2DFA\bin\NFA2DFA.class
     目录           0  2015-03-25 17:57  NFA2DFA\src\
     文件       15142  2015-04-24 08:48  NFA2DFA\src\NFA2DFA.java