automachine.java

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

				}
				// MessageDialog.openInformation(null,"提示",newState2.toString());
				unReadyStates.add(newState2);

				newStates.add(newState2);

			}
			// MessageDialog.openInformation(null,"提示",unReadyStates.toString());
			unReady = unReadyStates.iterator();

		}
		// MessageDialog.openInformation(null,"提示",newEndStates.toString());
		DFA.setStates(new Vector(newStates));
		DFA.setFunction(newFunction);
		DFA.setEndStates(new Vector(newEndStates));
		DFA.formatThreeRow(vecThreeRow);
		DFA.setIsE_NFA();
		DFA.setIsDFA();
		return DFA;
	}

	public AutoMachine ENFAtoNFA(AutoMachine machine){
		AutoMachine NFA = new AutoMachine(machine.getLabel() + "的NFA形式");
		NFA.maxcols = 2;
		NFA.setFirState(machine.getFirState());
		NFA.setLetters(machine.getLetters());
		NFA.getLetters().remove((Character)'ε');
		Set<String> newStates = new HashSet(machine.getStates());
		Set<String> newEndStates = new HashSet(machine.getEndStates());
		TransFunction newFunction = new TransFunction();
		Vector vecThreeRow = new Vector();
		Set setState = machine.getFunction().outputE_closure(machine.getFirState());
		Iterator temp = setState.iterator();
		
		while(temp.hasNext()){
			String state = (String)temp.next();
			if(machine.getEndStates().contains(state)){
				newEndStates.add(machine.getFirState());
				break;
			}
		}
		//MessageDialog.openInformation(null,"提示",newEndStates.toString());
		
		temp = newStates.iterator();
		while(temp.hasNext()){
			String state = (String)temp.next();		
			
			for(int i=0;i<NFA.getLetters().size(); i++){
				Set<String> lastStates = null;
				setState = null;
				char letter = NFA.getLetters().get(i);
				
				Set tempSet = null;
				tempSet = machine.getFunction().outputE_closure(state);
				Iterator stateE_closure = tempSet.iterator();
				while(stateE_closure.hasNext()){
					String state2 = (String)stateE_closure.next();
					Set stateE_closureSet = machine.getFunction().outputNextState(state2, letter);
					setState = setAddSet(setState,stateE_closureSet);
				}
				
				if(setState != null){
					
					stateE_closure = setState.iterator();
					while(stateE_closure.hasNext()){
						String state2 = (String)stateE_closure.next();
						Set stateE_closureSet = machine.getFunction().outputE_closure(state2);
						lastStates = setAddSet(lastStates,stateE_closureSet);
					}
					//MessageDialog.openInformation(null,"提示",lastStates.toString());
				}else
					continue;
				
				if(lastStates != null){
				String test = state+":"+letter+":"+lastStates.toString();
				//MessageDialog.openInformation(null,"提示",test);
				}			
				if(lastStates != null){
					stateE_closure = lastStates.iterator();
					while(stateE_closure.hasNext()){
						String state2 = (String)stateE_closure.next();
						newFunction.addFunction(state, letter, state2);
						String test = state+":"+letter+":"+state2.toString();
						vecThreeRow.add(test);
					}
				}
			}
		}
		NFA.setStates(new Vector(newStates));
		NFA.setEndStates(new Vector(newEndStates));
		NFA.setFunction(newFunction);
		NFA.formatThreeRow(vecThreeRow);
		NFA.setIsE_NFA();
		NFA.setIsDFA();
		return NFA;
	}
	
	public AutoMachine simplifyMachine(AutoMachine machine){
		AutoMachine simplifyDFA = new AutoMachine(machine.getLabel() + "的化简形式");
		simplifyDFA.maxcols = 2;
		Set<String> newStates = new HashSet<String>();
		String 		newFirState = null;
		Set<String> newEndStates = new HashSet<String>();
		simplifyDFA.setLetters(machine.getLetters());
		TransFunction newFunction = new TransFunction();
		Vector<ThreeRow> newVecThreeRow = new Vector<ThreeRow>();
		
		AutoMachine copy = copyOfMachine(machine);
		Set copyNewStates = copy.getFunction().outputStatesReachable(copy.getFirState());

		Set discardSet = new HashSet(new Vector(copy.getStates()));
		discardSet.removeAll(copyNewStates);
		Iterator copyStatesCyc = discardSet.iterator();

		while(copyStatesCyc.hasNext()){
			String state = (String)copyStatesCyc.next();
			copy.getFunction().getHashFunction().remove(state);
		}
		copy.setStates(new Vector(copyNewStates));
		
		Hashtable<Set,Boolean> hashSet = new Hashtable<Set,Boolean>();
		Hashtable<Set,String> lastHashSet = new Hashtable<Set,String>();
		hashSet = setFirstPartion(copy,hashSet);
		Enumeration e1 = hashSet.keys();
		while(hashSet.size()>0 && e1.hasMoreElements()  ){
			Set set1 = (Set)e1.nextElement();
			boolean isPartion = (Boolean)hashSet.get(set1);
			if(isPartion){
				//hashSet.remove(set1);
				lastHashSet.put(set1, "");
				if(hashSet.size() == 0)
					break;
				//e1 = hashSet.keys();
				continue;
			}
			lastHashSet.clear();
			hashSet = setTwoPartion(copy,set1,hashSet);
			e1 = hashSet.keys();
		}

		e1 = lastHashSet.keys();
		int i=0;
		while(e1.hasMoreElements()){
			Set set1 = (Set)e1.nextElement();
			String state = "q" + i++;
			if(set1.contains(copy.getFirState()))
				newFirState = state;
			Iterator set1Cyc = set1.iterator();
			while(set1Cyc.hasNext()){
				String state2 = (String)set1Cyc.next();
				if(copy.getEndStates().contains(state2))
					newEndStates.add(state);
			}
			lastHashSet.put(set1, state);
			newStates.add(state);
			//MessageDialog.openInformation(null,"提示",set1.toString());
		}
		Vector<ThreeRow> vectorThreeRow =  (Vector<ThreeRow>)copy.getThreeRow();
		for(i=0;i<vectorThreeRow.size();i++){
			boolean isSameClass = false;
			ThreeRow threeRow = (ThreeRow)vectorThreeRow.get(i);
			String state = threeRow.state;
			String state2 = threeRow.state2;
			if(discardSet.contains(state) || discardSet.contains(state2))
				continue;

			e1 = lastHashSet.keys();
			Set set1 = null,set2 = null;
			while(e1.hasMoreElements()){
				set1 = (Set)e1.nextElement();
				if(set1.contains(state))
					break;
			}
			e1 = lastHashSet.keys();
			while(e1.hasMoreElements()){
				set2 = (Set)e1.nextElement();
				if(set2.contains(state2))
					break;
			}
			state = (String)lastHashSet.get(set1);
			state2 = (String)lastHashSet.get(set2);
			for(int j=0;j<newVecThreeRow.size();j++){
				ThreeRow nthreeRow = (ThreeRow)newVecThreeRow.get(j);
				if(nthreeRow.isClassSame(state,threeRow.letter,state2)){
					isSameClass = true;
					break;
				}
			}
			if(isSameClass)
				continue;
			
			ThreeRow newThreeRow = new ThreeRow(state,threeRow.letter,state2);			
			newFunction.addFunction(state, threeRow.letter, state2);
			newVecThreeRow.add(newThreeRow);
		}

		simplifyDFA.setFirState(newFirState);
		simplifyDFA.setStates(new Vector(newStates));
		simplifyDFA.setEndStates(new Vector(newEndStates));
		simplifyDFA.setFunction(newFunction);
		return simplifyDFA;
	}
	
	private Hashtable<Set,Boolean> setFirstPartion(AutoMachine machine,Hashtable hash){
		Set set1 = new HashSet(machine.getEndStates());
		Set set2 = new HashSet(machine.getStates());
		set2.removeAll(set1);		
		hash.put(set1, false);
		hash.put(set2, false);
		
		return hash;
	}
	
	private Hashtable<Set,Boolean> setTwoPartion(AutoMachine machine,Set set1,Hashtable hash){
		
		if(set1.size() ==1){
			hash.put(set1, true);
			return hash;
		}
		boolean isInOneSet = true;
		for(int i=0;i<machine.getLetters().size();i++){
			char letter = machine.getLetters().get(i);
			Iterator setCyc = set1.iterator();
			Set<String> output = new HashSet<String>();
			String state = null;
			while(setCyc.hasNext()){
				state = (String)setCyc.next();
				Set outputSet = machine.getFunction().outputNextState(state, letter);
				if(outputSet == null)
					continue;
				Iterator temp = outputSet.iterator();
				while(temp.hasNext()){
					output.add((String)temp.next());
				}
			}
			//MessageDialog.openInformation(null,"提示",output.toString());
			
			//验证是否Vector的状态都在一个集合中			
			Object[] outputArray = new String[output.size()];
			outputArray = output.toArray();
			String state2 = outputArray[0].toString();
			Set oneSet = null;
			Enumeration e1 = hash.keys();
			while(e1.hasMoreElements()){
				Set tempSet = (Set)e1.nextElement();
				if(tempSet.contains(state2)){
					oneSet = tempSet;
					break;
				}
			}
			for(int j=1;j<outputArray.length;j++){
				state2 = outputArray[j].toString();
				if(!oneSet.contains(state2)){
					isInOneSet = false;
					break;
				}
			}
			if(!isInOneSet){
				hash.remove(set1);
				set1.remove(state);
				Set set2 = new HashSet();
				set2.add(state);
				hash.put(set1, false);
				hash.put(set2, false);
				break;
			}				

		}
		if(isInOneSet)
			hash.put(set1, true);
		return hash;
	}
	private AutoMachine copyOfMachine(AutoMachine machine){
		AutoMachine copy = new AutoMachine(machine.getLabel());
		copy.setFirState(machine.getFirState());
		copy.setStates(machine.getStates());
		copy.setEndStates(machine.getEndStates());
		copy.setLetters(machine.getLetters());
		copy.setFunction( copy.copyFunction(machine.getFunction()) );
		copy.setThreeRow(machine.getThreeRow());
		return copy;
	}
	private TransFunction copyFunction(TransFunction function) {
		// TODO 自动生成方法存根
		
		TransFunction newFunction = new TransFunction();
		Hashtable table = function.getHashFunction();
		Enumeration e = table.keys();
		while(e.hasMoreElements()){
			String key = (String)e.nextElement();
			Vector vec = (Vector)table.get(key);
			newFunction.getHashFunction().put(key, vec);
		}
		return newFunction;
	}

	private Set setAddSet(Set set1,Set set2){
		if(set2 == null)
			return set1;
		if(set1 == null)
			set1 = new HashSet();
		Iterator temp = set2.iterator();
		while(temp.hasNext()){
			String state = (String)temp.next();
			set1.add(state);
		}
		
		return set1;
	}
	private String changeSetToString(Set set) {
		if (set == null)
			return null;

		Iterator temp = set.iterator();
		String array = "";
		while (temp.hasNext()) {
			array = array + temp.next() + ",";

		}
		array = array.substring(0, array.length() - 1);
		return array;
	}

	public class ThreeRow {
		public String state;

		public char letter;

		public String state2;

		public ThreeRow(String state, char letter, String state2) {
			this.state = state;
			this.letter = letter;
			this.state2 = state2;
		}

		public String toString() {
			return state +":"+ letter + state2;
		}
		public boolean isClassSame(String nState1,char nLetter,String nState2){
			if(state.equals(nState1) && letter == nLetter
					&& state2.equals(nState2))
					return true;
			else 
				return false;
		}
	}

	public String toString() {
		return states.toString() + "\n" + letters.toString() + "\n"
				+ function.toString() + "\n" + endStates.toString();

	}

	public boolean isDFA() {
		return isDFA;
	}

	public void setDFA(boolean isDFA) {
		this.isDFA = isDFA;
	}

	public boolean isE_NFA() {
		return isE_NFA;
	}

	public int getHLines() {
		return hLines;
	}

	public Vector<ThreeRow> getThreeRow() {
		return threeRow;
	}

	public int getVLines() {
		return vLines;
	}

	public void setThreeRow(Vector<ThreeRow> threeRow) {
		this.threeRow = threeRow;
	}

}