confirmnfa.java

本程序是编译原理的经典试验

/**
 * 基于状态转换矩阵表示的FA确定化、最小化并给出有限自动机的通用实现
 * @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[][];					/* 存放待确定化的非确定有限自动机的状态转换矩阵 */
	private String matrix_DFA[][];					/* 存放确定化后的状态转换矩阵 */
	private char input_SYM[];						/* 存放输入符号，初始符号集包含e(在数组尾端)，确定化之后去掉e，长度减1 */
	private char endStatus_NFA[];				/* 存放NFA的终态集 */
	private String end_Status;

	private ArrayList c_Group;						/* 存放根据NFA构造出来的C子集 */

	private int len_SYMS;							/* 存放输入符号长度，input_SYM数组的长度 */
	private int len_ENDSTNFA;					/* 存放NFA终态集的长度，endStatus_NFA数组的长度 */
	private int row_NFA, col_NFA;				/* 存放最初NFA状态转换矩阵(matrix_NFA)的行数及列数，其中col_NFA比实际矩阵列数小1  */
	private int index_CGroup;						/* 存放在c_Group中游走的下标 */
	private int counter;								/* 子集中的状态计数器 */
	private int row_DFA, col_DFA;				/* 存放确定化之后的状态转换矩阵(matrix_DFA)行数及列数，其中col_DFA比实际矩阵列数小1*/

	/**
	 * DFA的最小化
	 * 思想：
	 * 1.首先去掉无用状态: a.任何状态都不能到达的状态 b.从这个状态没有通路到达终态
	 * 2.合并等价状态：
	 * 		a.一致性条件：状态s和状态t必须同时为可接受状态(初态)或不可接受状态(终态)
	 * 		b.蔓延性条件：对以所有输入符号，状态s和状态t必须转换到等价的状态里
	 */
	public void miniDFA() {
		String start = "", end = "";					/* start为初态集，end为终态集 */
		boolean isUniform = true;
		ArrayList strOnly;								/* 存放P集合，与p_Group不同之处是只存放字符串，儿p_Group存放PStatus对象 */

		removeExcrescent();							/* 删除无用状态，未完全实现 */
		strOnly = divide();								/* 分割成初态集和终态集的列表 */
		start = strOnly.get(0).toString();			/* 初态集赋值 */
		end = strOnly.get(1).toString();			/* 终态集赋值 */

		/*
		 * 从状态0开始与之后的每一个状态进行匹配，如果有等价状态则合并状态
		 * 将与当前状态等价的状态
		 */
		while(isUniform) {
			for(int i = 0; i < row_DFA; i++) {						/* 当前状态循环 */
				if(!matrix_DFA[i][0].equals("@")) {					/* 如果该状态被合并，则跳过此状态，继续下一个状态 */
					for(int j = i + 1; j < row_DFA; j++) {			/* 寻找与当前状态等价的状态的循环 */
						if(!matrix_DFA[j][0].equals("@")) {			/* 如果该状态已被合并，则跳过此状态，继续下一个状态 */
							String first = matrix_DFA[i][1];			/* 获取当前状态在第一个输入符号下的跳转状态 */
							String next = matrix_DFA[j][1];			/* 获取待匹配状态在第一个输入符号下的跳转状态 */
							/* 当前状态和待匹配状态的首个输入符号下的跳转状态相同，当前状态和待匹配状态在同一个集合中(可接受或不可接受)*/
							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++) {	/* 接续判断之后所有输入符号下跳转状态是否相同*/
									String first2 = matrix_DFA[i][k];		
									String next2 = matrix_DFA[j][k];
									if(!first2.equals(next2)) {					/* 如果在同一个输入符号下，跳转状态不相同，则放弃继续到下一个状态 */
										isUniform = false;
										break;
									}
								}
								if(isUniform) {									/* 如果所有输入下跳转状态都相同，则合并，即对待匹配状态进行标记 */
									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] = "@";					/* 对待匹配状态进行标记 */
									continue;
								}
							}
						}
					}
				}
			}	
		}

		/* 确定最小化DFA终态 */
		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;
			}
		}
	}
	/**
	 * 将状态子集分割成初态集和终态集
	 */
	public ArrayList divide() {
		String sStatus = "";								/* 初态集 */
		String eStatus = "";								/* 终态集 */
		ArrayList arrayList = new ArrayList();

		for(int i = 0; i < c_Group.size(); i++) {		/* 对C子集的每个元素(确定化之后的状态集)进行检测 */
			if(!((ClosureStatus)c_Group.get(i)).getST().equals("@")) {		/* 如果该状态不是无用状态，继续执行 */
				int j;
				for(j = 0; j < len_ENDSTNFA; j++) {
					if(((ClosureStatus)c_Group.get(i)).getSTATUS().contains("" + endStatus_NFA[j])) {	/* 如果状态集包含最初NFA的终态，则被加入到终态集 */
						eStatus += ((ClosureStatus)c_Group.get(i)).getST();			/* 将字符标记添加到终态集中 */
						break;
					}
				}
				if(j >= len_ENDSTNFA) {						/* 其余添加到初态集中 */
					sStatus += ((ClosureStatus)c_Group.get(i)).getST();
				}
			}
		}
		arrayList.add(sStatus);
		arrayList.add(eStatus);
		return arrayList;
	}
	/**
	 * 删除无用状态
	 * 用@做标记
	 */
	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("@");
			}
		}
	}
	/**
	 * 判断是否为无用状态
	 * @param status
	 * @return
	 */
	public boolean exit(String status) {
		boolean exit = false;

		for(int i = 0; i < row_DFA; 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;
	}

	/**
	 * 将确定化之后的状态集用一个字符表示：0~9序列
	 */
	private void strToChar() {
		String moveStatus;							/* 存放子集成员在a输入下的状态转换集 */
		String closureStatus;							/* 存放在moveStatus的闭包集 */
		row_DFA = c_Group.size();					/* 利用C子集族中的元素个数定义 */
		col_DFA = len_SYMS - 1;					/* 确定化之后去掉了输入符号e，所以减1 */
		matrix_DFA = new String[row_DFA][col_DFA + 1];								/* + 1 是为了在每一行开头存放状态位 */

		for(int i = 0; i < c_Group.size(); i++) {/* 检测所有状态在所有输入符号下的跳转状态，并重新构造状态转换矩阵 */
			ClosureStatus newCS = (ClosureStatus)c_Group.get(i);
			matrix_DFA[i][0] = newCS.getST();				/* 每一行开头添加状态标记 */
			String tempStr = newCS.getSTATUS();
			for(int j = 1; j <= col_DFA; j++) {
				moveStatus = move(tempStr, j, matrix_NFA);			/* 求状态在J输入下的跳转状态 */
				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;
					}
				}
			}
		}
	}
	/**
	 * 将状态集中的状态从小到大排序
	 * @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;
	}
	/**
	 * 删除状态集中重复的状态
	 * @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;
	}
	/**
	 * 求一个状态集在input输入下的跳转状态