automachine.java

有限自动机输入,转换,识别,图形显示与化简

package cn.work.zdj.sys;

import java.util.Enumeration;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Set;
import java.util.Vector;

import org.eclipse.jface.dialogs.MessageDialog;

public class AutoMachine {
	private String label;

	private Vector<String> states;

	private Vector<Character> letters;

	private TransFunction function;

	private String firState;

	private Vector<String> endStates;

	private Vector<ThreeRow> threeRow;

	private int[][] map;

	private int hLines = 5;

	private int vLines = 6;
	public int maxcols = 3;
	private boolean isDFA = true;
	private boolean isE_NFA = true;

	public Vector<Character> getLetters() {
		return letters;
	}

	public void setLetters(Vector<Character> letters) {
		this.letters = letters;
	}

	public Vector<String> getStates() {
		return states;
	}

	public void setStates(Vector<String> states) {
		this.states = states;
	}

	public TransFunction getFunction() {
		return function;
	}

	public void setFunction(TransFunction function) {
		this.function = function;
	}

	public AutoMachine(String label) {
		this.label = label;

		map = new int[hLines][vLines];
		clearMap();

	}

	public void clearMap() {
		for (int i = 0; i < hLines; i++) {
			for (int j = 0; j < vLines; j++)
				map[i][j] = 0;

		}
	}

	public void Init(Vector<String> states, Vector letters, Hashtable functions,
			String firState, Vector endStates, Vector threeRow) {
		this.states = states;
		this.letters = letters;
		this.function = new TransFunction(functions);
		this.firState = firState;
		this.endStates = endStates;
		formatThreeRow(threeRow);
		
		setIsE_NFA();
		setIsDFA();
		
		// MessageDialog.openError(null,"提示",this.firState.toString());
	}

	private void setIsDFA() {
		if( isE_NFA ){
			isDFA = false;
			return;
		}
		for (int i = 0; i < threeRow.size(); i++) {
			ThreeRow row = (ThreeRow) threeRow.get(i);
			Set set = function.outputNextState(row.state, row.letter);

			if (set != null && set.size() > 1) {
				//MessageDialog.openError(null,"提示",row.state+":"+row.letter+":"+set.toString());			
				isDFA = false;
				break;
			}
		}
	}

	private void setIsE_NFA(){
		if(letters.contains('ε'))
			isE_NFA = true;
		else
			isE_NFA = false;
	}
	private void formatThreeRow(Vector threeRow) {
		this.threeRow = new Vector<ThreeRow>();

		for (int i = 0; i < threeRow.size(); i++) {
			String row = (String) threeRow.get(i);
			String[] states = row.split(":");
			ThreeRow temp = new ThreeRow(states[0], states[1].charAt(0),
					states[2]);
			this.threeRow.add(temp);
			// MessageDialog.openError(null,"提示",temp.toString());
		}

	}

	public void addState(String state) {
		states.add(state);
	}

	public void addLetter(char letter) {
		letters.add(letter);
	}

	public void addFunction(String state, char letter, String state2) {
		function.addFunction(state, letter, state2);
	}

	public void addEndState(String endState) {
		endStates.add(endState);
	}

	public String getLabel() {
		return label;
	}

	public void setLabel(String label) {
		this.label = label;
	}

	public String getFirState() {
		return firState;
	}

	public void setFirState(String firState) {
		this.firState = firState;
	}

	public Vector<String> getEndStates() {
		return endStates;
	}

	public void setEndStates(Vector<String> endStates) {
		this.endStates = endStates;
	}

	public boolean isValidate() {

		// 状态集要包含初始状态
		if (!states.contains(firState))
			return false;

		// 状态集要包含终止状态集
		for (int i = 0; i < endStates.size(); i++) {
			if (!states.contains(endStates.get(i)))
				return false;

		}
		// 转换函数中涉及的状态必须在状态集中,涉及的字母必须在字母表中
		Hashtable functions = function.getHashFunction();
		Enumeration e = functions.keys();
		while (e.hasMoreElements()) {
			String state = (String) e.nextElement();
			if (!states.contains(state))
				return false;
			Vector value = (Vector) functions.get(state);
			for (int i = 0; i < value.size(); i++) {
				Hashtable temp = (Hashtable) value.get(i);
				Enumeration e1 = temp.keys();
				while (e1.hasMoreElements()) {
					Character letter = (Character) e1.nextElement();
					if (!letters.contains(letter.charValue()))
						return false;

					String endState = (String) temp.get(letter);
					if (!states.contains(endState))
						return false;
				}
			}
		}
		return true;
	}

	public void placeMap() {
		
		clearMap();
		for (int k = 1; k <= states.size(); k++) {
			if (k == 1) {
				map[0][0] = k;
				continue;
			}
			for (int i = 1; i <= map.length; i++) {
				boolean flag = false;
				for (int j = 1; j < map[0].length; j++) {
					if (place(i, j, map)) {
						map[i - 1][j - 1] = k;
						flag = true;
						break;
					}
				}
				if (flag)
					break;
			}
		}
		maxcols = this.maxcols;
	}

	private boolean place(int i, int j, int[][] map) {
		if (map[i - 1][j - 1] != 0)
			return false;
		int maxcols = this.maxcols;
		for (int k = 0; k < map[0].length; k++) {
			if (map[i - 1][k] != 0)
				maxcols--;
			if (maxcols <= 0)
				return false;
		}

		if (i - 1 >= 1 && map[i - 2][j - 1] != 0)
			return false;
		if (i + 1 <= map.length && map[i][j - 1] != 0)
			return false;
		if (j - 1 >= 1 && map[i - 1][j - 2] != 0)
			return false;
		if (j + 1 <= map[0].length && map[i - 1][j] != 0)
			return false;
		return true;
	}

	public int[][] getMap() {
		return map;
	}

	public AutoMachine NFAtoDFA(AutoMachine machine) {
		AutoMachine DFA = new AutoMachine(machine.getLabel() + "的DFA形式");
		DFA.maxcols = 2;
		DFA.setFirState("[" + machine.getFirState() + "]");
		DFA.setLetters(machine.getLetters());
		Set<String> newStates = new HashSet();
		Set<String> newEndStates = new HashSet();
		TransFunction newFunction = new TransFunction();

		Set<String> readyStates = new HashSet();
		Set<String> unReadyStates = new HashSet();
		Vector vecThreeRow = new Vector();
		Enumeration e1 = machine.getFunction().getHashFunction().keys();

		while (e1.hasMoreElements()) {
			String state = (String) e1.nextElement();
			if (machine.getEndStates().contains(state))
				newEndStates.add("[" + state + "]");

			HashSet<Character> letters = (HashSet) machine.getFunction()
					.getStateLetters(state);
			Iterator temp = letters.iterator();

			//MessageDialog.openInformation(null,"提示",state+letters.toString());
			while (temp.hasNext()) {
				char letter = (Character) temp.next();
				Set state2 = machine.getFunction().outputNextState(state,
						letter);

				Iterator temp2 = state2.iterator();
				String newState = "[";
				boolean isEndState = false;
				while (temp2.hasNext()) {
					String oldState = temp2.next().toString();
					newState = newState + oldState.trim() + ",";
					isEndState = isEndState
							|| machine.getEndStates().contains(oldState);

				}

				newState = newState.substring(0, newState.length() - 1);

				newState = newState + "]";
				newStates.add(newState);
				if (isEndState)
					newEndStates.add(newState);
				newStates.add("[" + state + "]");
				readyStates.add("[" + state + "]");
				unReadyStates.add(newState);
				// MessageDialog.openInformation(null,"提示",newState);
				newFunction.addFunction("[" + state + "]", letter, newState);
				String threeRow = "[" + state + "]"+ ":"+letter+":"+ newState;
				vecThreeRow.add(threeRow);
			}

		}
		// MessageDialog.openInformation(null,"提示",readyStates.toString()+"|"+unReadyStates.toString()+"|"+newStates.toString()+"|"+newFunction.toString());

		Iterator unReady = unReadyStates.iterator();
		while (unReady.hasNext()) {
			String state = (String) unReady.next();
			// MessageDialog.openInformation(null,"提示",state.toString());

			if (readyStates.contains(state)) {
				unReadyStates.remove(state);
				unReady = unReadyStates.iterator();
				continue;
			}

			unReadyStates.remove(state);
			readyStates.add(state);
			String state2 = new String(state);
			state = state.substring(1, state.length() - 1);

			String[] states = state.split(",");

			for (int k = 0; k < machine.getLetters().size(); k++) {
				char letter = machine.getLetters().get(k);
				String newState2 = "";
				boolean isEndState = false;
				Set newStateSet = new HashSet();
				for (int i = 0; i < states.length; i++) {
					Set states2 = machine.getFunction().outputNextState(
							states[i], letter);
					if (states2 == null)
						continue;

					// newState2 = newState2 +
					// machine.getFunction().outputNextStateString(states[i],
					// letter)+",";

					Iterator temp = states2.iterator();
					while (temp.hasNext()) {
						newStateSet.add(temp.next());
					}

					Set isEndStateSet = machine.getFunction().outputNextState(
							states[i], letter);

					if (isEndStateSet != null) {

						Iterator isEnd = isEndStateSet.iterator();
						while (isEnd.hasNext()) {
							isEndState = isEndState
									|| machine.getEndStates().contains(
											isEnd.next());
							if (isEndState)
								break;
						}
					}

					// MessageDialog.openInformation(null,"提示",states[i]+":"+letter+":"+newState2.toString());

				}
				if (newStateSet.size() == 0)
					continue;

				// newState2 = newState2.substring(0,newState2.length()-1);
				newState2 = changeSetToString(newStateSet);
				newState2 = "[" + newState2 + "]";
				// MessageDialog.openInformation(null,"提示",newState2.toString());

				if (isEndState)
					newEndStates.add(newState2);

				newFunction.addFunction(state2, letter, newState2);
				String threeRow =  state2 +":"+ letter+":"+ newState2;
				vecThreeRow.add(threeRow);
				if (readyStates.contains(newState2)) {

					continue;