/**
 * 基于狀態(tài)轉(zhuǎn)換矩陣表示的FA確定化、最小化并給出有限自動(dòng)機(jī)的通用實(shí)現(xiàn)
 * @author Skypia0000
 *
 */

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

@SuppressWarnings(value = {"unchecked"})
public class ConfirmNFA {
	private String matrix_NFA[][];					/* 存放待確定化的非確定有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換矩陣 */
	private String matrix_DFA[][];					/* 存放確定化后的狀態(tài)轉(zhuǎn)換矩陣 */
	private char input_SYM[];						/* 存放輸入符號(hào)，初始符號(hào)集包含e(在數(shù)組尾端)，確定化之后去掉e，長(zhǎng)度減1 */
	private char endStatus_NFA[];				/* 存放NFA的終態(tài)集 */
	private String end_Status;

	private ArrayList c_Group;						/* 存放根據(jù)NFA構(gòu)造出來的C子集 */

	private int len_SYMS;							/* 存放輸入符號(hào)長(zhǎng)度，input_SYM數(shù)組的長(zhǎng)度 */
	private int len_ENDSTNFA;					/* 存放NFA終態(tài)集的長(zhǎng)度，endStatus_NFA數(shù)組的長(zhǎng)度 */
	private int row_NFA, col_NFA;				/* 存放最初NFA狀態(tài)轉(zhuǎn)換矩陣(matrix_NFA)的行數(shù)及列數(shù)，其中col_NFA比實(shí)際矩陣列數(shù)小1  */
	private int index_CGroup;						/* 存放在c_Group中游走的下標(biāo) */
	private int counter;								/* 子集中的狀態(tài)計(jì)數(shù)器 */
	private int row_DFA, col_DFA;				/* 存放確定化之后的狀態(tài)轉(zhuǎn)換矩陣(matrix_DFA)行數(shù)及列數(shù)，其中col_DFA比實(shí)際矩陣列數(shù)小1*/

	/**
	 * DFA的最小化
	 * 思想：
	 * 1.首先去掉無用狀態(tài): a.任何狀態(tài)都不能到達(dá)的狀態(tài) b.從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)
	 * 2.合并等價(jià)狀態(tài)：
	 * 		a.一致性條件：狀態(tài)s和狀態(tài)t必須同時(shí)為可接受狀態(tài)(初態(tài))或不可接受狀態(tài)(終態(tài))
	 * 		b.蔓延性條件：對(duì)以所有輸入符號(hào)，狀態(tài)s和狀態(tài)t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里
	 */
	public void miniDFA() {
		String start = "", end = "";					/* start為初態(tài)集，end為終態(tài)集 */
		boolean isUniform = true;
		ArrayList strOnly;								/* 存放P集合，與p_Group不同之處是只存放字符串，兒p_Group存放PStatus對(duì)象 */

		removeExcrescent();							/* 刪除無用狀態(tài)，未完全實(shí)現(xiàn) */
		strOnly = divide();								/* 分割成初態(tài)集和終態(tài)集的列表 */
		start = strOnly.get(0).toString();			/* 初態(tài)集賦值 */
		end = strOnly.get(1).toString();			/* 終態(tài)集賦值 */

		/*
		 * 從狀態(tài)0開始與之后的每一個(gè)狀態(tài)進(jìn)行匹配，如果有等價(jià)狀態(tài)則合并狀態(tài)
		 * 將與當(dāng)前狀態(tài)等價(jià)的狀態(tài)
		 */
		while(isUniform) {
			for(int i = 0; i < row_DFA; i++) {						/* 當(dāng)前狀態(tài)循環(huán) */
				if(!matrix_DFA[i][0].equals("@")) {					/* 如果該狀態(tài)被合并，則跳過此狀態(tài)，繼續(xù)下一個(gè)狀態(tài) */
					for(int j = i + 1; j < row_DFA; j++) {			/* 尋找與當(dāng)前狀態(tài)等價(jià)的狀態(tài)的循環(huán) */
						if(!matrix_DFA[j][0].equals("@")) {			/* 如果該狀態(tài)已被合并，則跳過此狀態(tài)，繼續(xù)下一個(gè)狀態(tài) */
							String first = matrix_DFA[i][1];			/* 獲取當(dāng)前狀態(tài)在第一個(gè)輸入符號(hào)下的跳轉(zhuǎn)狀態(tài) */
							String next = matrix_DFA[j][1];			/* 獲取待匹配狀態(tài)在第一個(gè)輸入符號(hào)下的跳轉(zhuǎn)狀態(tài) */
							/* 當(dāng)前狀態(tài)和待匹配狀態(tài)的首個(gè)輸入符號(hào)下的跳轉(zhuǎn)狀態(tài)相同，當(dāng)前狀態(tài)和待匹配狀態(tài)在同一個(gè)集合中(可接受或不可接受)*/
							if(first.equals(next) && ((start.contains(first) && start.contains(next)) || (end.contains(next) && end.contains(next)))) {//bug
								isUniform = true;
								for(int k = 2; k <= col_DFA; k++) {	/* 接續(xù)判斷之后所有輸入符號(hào)下跳轉(zhuǎn)狀態(tài)是否相同*/
									String first2 = matrix_DFA[i][k];		
									String next2 = matrix_DFA[j][k];
									if(!first2.equals(next2)) {					/* 如果在同一個(gè)輸入符號(hào)下，跳轉(zhuǎn)狀態(tài)不相同，則放棄繼續(xù)到下一個(gè)狀態(tài) */
										isUniform = false;
										break;
									}
								}
								if(isUniform) {									/* 如果所有輸入下跳轉(zhuǎn)狀態(tài)都相同，則合并，即對(duì)待匹配狀態(tài)進(jìn)行標(biāo)記 */
									for(int m = 0; m < row_DFA; m++) {
										for(int n = 1; n <= col_DFA; n++) {
											if(matrix_DFA[m][n].equals(matrix_DFA[j][0])) {
												matrix_DFA[m][n] = matrix_DFA[i][0];
											}
										}
									}
									matrix_DFA[j][0] = "@";					/* 對(duì)待匹配狀態(tài)進(jìn)行標(biāo)記 */
									continue;
								}
							}
						}
					}
				}
			}	
		}

		/* 確定最小化DFA終態(tài) */
		for(int i = 0; i < row_DFA; i++) {
			if(matrix_DFA[i][0].equals("@")) {continue;}
			if(end.contains(matrix_DFA[i][0])) {
				end_Status = matrix_DFA[i][0];
				break;
			}
		}
	}
	/**
	 * 將狀態(tài)子集分割成初態(tài)集和終態(tài)集
	 */
	public ArrayList divide() {
		String sStatus = "";								/* 初態(tài)集 */
		String eStatus = "";								/* 終態(tài)集 */
		ArrayList arrayList = new ArrayList();

		for(int i = 0; i < c_Group.size(); i++) {		/* 對(duì)C子集的每個(gè)元素(確定化之后的狀態(tài)集)進(jìn)行檢測(cè) */
			if(!((ClosureStatus)c_Group.get(i)).getST().equals("@")) {		/* 如果該狀態(tài)不是無用狀態(tài)，繼續(xù)執(zhí)行 */
				int j;
				for(j = 0; j < len_ENDSTNFA; j++) {
					if(((ClosureStatus)c_Group.get(i)).getSTATUS().contains("" + endStatus_NFA[j])) {	/* 如果狀態(tài)集包含最初NFA的終態(tài)，則被加入到終態(tài)集 */
						eStatus += ((ClosureStatus)c_Group.get(i)).getST();			/* 將字符標(biāo)記添加到終態(tài)集中 */
						break;
					}
				}
				if(j >= len_ENDSTNFA) {						/* 其余添加到初態(tài)集中 */
					sStatus += ((ClosureStatus)c_Group.get(i)).getST();
				}
			}
		}
		arrayList.add(sStatus);
		arrayList.add(eStatus);
		return arrayList;
	}
	/**
	 * 刪除無用狀態(tài)
	 * 用@做標(biāo)記
	 */
	public void removeExcrescent() {
		for(int i = 1; i < row_DFA; i++) {
			if(!exit(matrix_DFA[i][0])) {
				matrix_DFA[i][0] = "@";
				((ClosureStatus)c_Group.get(i)).setST("@");
			}
		}
	}
	/**
	 * 判斷是否為無用狀態(tài)
	 * @param status
	 * @return
	 */
	public boolean exit(String status) {
		boolean exit = false;

		for(int i = 0; i < row_DFA; i++) {
			/* 檢查除自身以外的狀態(tài)  */
			if(!status.equals(matrix_DFA[i][0])) {
				for(int j = 1; j < col_DFA + 1; j++) {
					if(status.equals(matrix_DFA[i][j])) {
						exit = true;
						i = row_DFA;
						break;
					}
				}
			}
		}
		//haven't been completed..........
		if(exit) {

		}

		return exit;
	}

	/**
	 * 將確定化之后的狀態(tài)集用一個(gè)字符表示：0~9序列
	 */
	private void strToChar() {
		String moveStatus;							/* 存放子集成員在a輸入下的狀態(tài)轉(zhuǎn)換集 */
		String closureStatus;							/* 存放在moveStatus的閉包集 */
		row_DFA = c_Group.size();					/* 利用C子集族中的元素個(gè)數(shù)定義 */
		col_DFA = len_SYMS - 1;					/* 確定化之后去掉了輸入符號(hào)e，所以減1 */
		matrix_DFA = new String[row_DFA][col_DFA + 1];								/* + 1 是為了在每一行開頭存放狀態(tài)位 */

		for(int i = 0; i < c_Group.size(); i++) {/* 檢測(cè)所有狀態(tài)在所有輸入符號(hào)下的跳轉(zhuǎn)狀態(tài)，并重新構(gòu)造狀態(tài)轉(zhuǎn)換矩陣 */
			ClosureStatus newCS = (ClosureStatus)c_Group.get(i);
			matrix_DFA[i][0] = newCS.getST();				/* 每一行開頭添加狀態(tài)標(biāo)記 */
			String tempStr = newCS.getSTATUS();
			for(int j = 1; j <= col_DFA; j++) {
				moveStatus = move(tempStr, j, matrix_NFA);			/* 求狀態(tài)在J輸入下的跳轉(zhuǎn)狀態(tài) */
				closureStatus = moveStatus;
				closureStatus = sort(removeEcho(closure(moveStatus, closureStatus, len_SYMS)));
				for(int k = 0; k < c_Group.size(); k++) {
					if(closureStatus.equals(((ClosureStatus)c_Group.get(k)).getSTATUS())) {
						matrix_DFA[i][j] = ((ClosureStatus)c_Group.get(k)).getST();
						break;
					}
				}
			}
		}
	}
	/**
	 * 將狀態(tài)集中的狀態(tài)從小到大排序
	 * @param str
	 * @return
	 */
	public String sort(String str){
		char[] s=str.toCharArray();
		String strs="";
		for(int i=0;i<str.length();i++) {
			char temp=s[str.length()-(1+i)];
			for(int j=str.length()-1;j>=1;j--){
				if(s[j]<s[j-1]){
					temp=s[j];
					s[j]=s[j-1];
					s[j-1]=temp;
				}
			}
		}
		for(int m=0;m<s.length;m++)
			strs+=s[m];
		return strs;
	}
	/**
	 * 刪除狀態(tài)集中重復(fù)的狀態(tài)
	 * @param str
	 * @return
	 */
	public String removeEcho(String str) {
		String tempStr = "";
		for(int i=0;i<str.length();i++){
			if(!tempStr.contains(String.valueOf(str.charAt(i)))) {
				tempStr+=String.valueOf(str.charAt(i));
			}
		}
		return tempStr;
	}
	/**
	 * 求一個(gè)狀態(tài)集在input輸入下的跳轉(zhuǎn)狀態(tài)