transfunction.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 TransFunction {
	private Hashtable hashFunction;
	
	public TransFunction(){
		hashFunction = new Hashtable();
	}
	public TransFunction(Hashtable hashFunction){
		this.hashFunction = hashFunction;
	}
	public void  addFunction(String state,char letter,String state2){
		Hashtable<Character,String> hash = new Hashtable();
		hash.put(letter, state2);
		Vector<Hashtable> vec = null;

		if(!hashFunction.containsKey(state)){
			vec= new Vector();
			this.hashFunction.put(state, vec);
		}else{
			vec = (Vector)hashFunction.get(state);
		}		
		
		vec.add(hash);		
		//MessageDialog.openInformation(null,"提示",state.toString()+":"+vec.toString());
		
	}
	public String toString(){
		Enumeration e = hashFunction.keys();
		String hash = "";
		while(e.hasMoreElements()){
			String key = (String)e.nextElement();
			hash = hash + key;
			Vector vec = (Vector)hashFunction.get(key);
			hash = hash +":" +vec.toString();
		}
		return hash;
	}
	public Set outputNextState(String state,char letter){
		Vector temp = (Vector)hashFunction.get(state);
		Set<String> vecState2 = null;
		if(temp != null){
			for(int i=0;i<temp.size();i++){
				Hashtable hash = (Hashtable)temp.get(i);
				
				if(!hash.containsKey(letter))
					continue;
				String state2 = hash.get(letter).toString();
				if(vecState2 == null)
					vecState2 = new HashSet<String>();
				vecState2.add(state2);
				
			}
		}
		
		return vecState2;
	}
	public String outputNextStateString(String state,char letter){
		Set set = outputNextState(state,letter);
		if(set == null)
			return null;
		Iterator temp = set.iterator();
		String states = "";
		
		while(temp.hasNext()){
			
			states = states+(String)temp.next()+",";
		}
		states = states.substring(0, states.length()-1);
		return states;
	}
	public Hashtable outputNextStatePossible(String state){
		Hashtable outputState = null;
		Vector temp = (Vector)hashFunction.get(state);
		if(temp == null)
			return null;
		for(int i=0;i<temp.size();i++){
			Hashtable<Character,String> hash = (Hashtable)temp.get(i);
			
			Enumeration e1 = hash.keys();
			String state2 = null;
			String letters = null;
			char letter = 0;
			while(e1.hasMoreElements()){
				letter = (Character)e1.nextElement();
				
				state2 = (String)hash.get(letter);  
			}
			letters = String.valueOf(letter);
			if(outputState == null)
				outputState = new Hashtable();
			if(outputState.containsKey(state2)){
				String str = (String)outputState.get(state2);
			
				outputState.put(state2, str+","+letters);
			}else
				outputState.put(state2, letters);
					
		}
		return outputState;
	}
	public Set outputE_closure(String state){
		Vector temp = (Vector)hashFunction.get(state);
		Set<String>vecState2 = new HashSet<String>();
		vecState2.add(state);
		if(temp != null){
			Set<String> unReadyStates = null;
			Set<String> readyStates = new HashSet<String>();
			for(int i=0;i<temp.size();i++){
				Hashtable hash = (Hashtable)temp.get(i);
				
				if(!hash.containsKey('ε'))
					continue;
				String state2 = hash.get('ε').toString();
				if(unReadyStates == null)
					unReadyStates = new HashSet<String>();
				unReadyStates.add(state2);
				
			}
			if(unReadyStates == null)
				return vecState2;
			Iterator unReady = unReadyStates.iterator();
			
			while (unReady.hasNext()) {
				if (readyStates.contains(state)) {
					unReadyStates.remove(state);
					unReady = unReadyStates.iterator();
					continue;
				}
				String strState = (String) unReady.next();
				unReadyStates.remove(strState);
				readyStates.add(strState);
				vecState2.add(strState);
				
				temp = (Vector)hashFunction.get(strState);
				for(int i=0;i<temp.size();i++){
					Hashtable hash = (Hashtable)temp.get(i);
					if(!hash.containsKey('ε'))
						continue;
					String state2 = hash.get('ε').toString();
					unReadyStates.add(state2);
					
				}
				unReady = unReadyStates.iterator();
			}
		}
		return vecState2;
	}
	
	public Set outputStatesReachable(String state){
		Set<String> outputReachable = new HashSet<String>();
		outputReachable.add(state);
		Set<String> unReadySet = new HashSet<String>();
		Set<String> readySet   = new HashSet<String>();
		unReadySet.add(state);
		
		Iterator unReadyCyc = unReadySet.iterator();
		while(unReadyCyc.hasNext()){
			String tempState = (String)unReadyCyc.next();
			if(readySet.contains(tempState)){
				unReadySet.remove(tempState);
				unReadyCyc = unReadySet.iterator();
				continue;
			}
			unReadySet.remove(tempState);
			readySet.add(tempState);
			outputReachable.add(tempState);
			Hashtable hash =  outputNextStatePossible(tempState);
			if(hash == null)
				continue;
			Enumeration e1 = hash.keys();
			String state2  = null;
			while(e1.hasMoreElements()){
				state2 = (String)e1.nextElement();
				unReadySet.add(state2);
				
			}
			unReadyCyc = unReadySet.iterator();
		}
		
		return outputReachable;
	}
	public Set getStateLetters(String state){
		Set<Character> letters = null;
		if(hashFunction.containsKey(state)){
			letters = new HashSet<Character>();
			Vector temp = (Vector)hashFunction.get(state);
			for(int i=0;i<temp.size();i++){
				Hashtable hash = (Hashtable)temp.get(i);
				Enumeration e1 = hash.keys();
				
				while(e1.hasMoreElements()){
					char letter = (Character)e1.nextElement();
					
					letters.add(letter);
				}
			}
			return letters;
		}else
			return null;
	}
	public Hashtable getHashFunction(){
		return hashFunction;
	}
}