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