package?lexicalanalyzer;
import?java.util.ArrayList;
import?java.util.Collections;
import?java.util.Stack;

public?class?DFA?{
	
	private?ArrayList?states=new?ArrayList（）;?
	private?NFA?nfa;
	private?DFAState?startState;
	private?ArrayList?endStates=new?ArrayList（）;
	
	public?static?DFA?newInstance（NFA?nfa）{
		return?new?DFA（nfa）;
	}
	
	public?DFA（NFA?nfa）{
		this.nfa=nfa;
		createDFA（nfa）;		
	}
		
	public?void?minimize（）{
		ArrayList>?workspace=
			new?ArrayList>（）;
		for（DFAState?state?:?getStates（））{
			ArrayList?moveTable=new?ArrayList（）;
			for（char?eachChar?:?getAlphabet（））{				
				if（state.move（eachChar）==null）{
					moveTable.add（-1）;
				}
				else{
					moveTable.add（state.move（eachChar）.getID（））;		
				}	
			}			
			workspace.add（moveTable）;		
		}
		//partition.
		ArrayList>?partition=
			new?ArrayList>（）;
		partition.add（this.endStates）;
		boolean[]?visited=new?boolean[workspace.size（）];
		for（int?i=0;i			if（visited[i]==true）{
				continue;
			}
			ArrayList?temp=new?ArrayList（）;
			temp.add（states.get（i））;
			for（int?j=i+1;j				if（workspace.get（i）.equals（workspace.get（j）））{
					visited[j]=true;
					if?（!endStates.contains（states.get（j）））?{
						temp.add（states.get（j））;
					}
				}
			}
			partition.add（temp）;	
		}
		selectRepresent（partition）;	
	}
	
	public?ArrayList?getStates（）{		
		return?states;
	}
	
	public?DFAState?getStartState（）{
		return?this.startState;
	}
	
	public?ArrayList?getEndStates（）{
		return?endStates;
	}
	
	public?ArrayList?getAlphabet（）{
		return?nfa.getAlphabet（）;
	}

	private?void?createDFA（NFA?nfa）{
		Stack?untagedStates=new?Stack（）;
		DFAState?start=new?DFAState（）;
		start.addAll（nullClosure（nfa.getStartState（）））;
		states.add（start）;
		setStartState（start）;
		untagedStates.push（start）;
		while（!untagedStates.empty（））{
			DFAState?current=untagedStates.pop（）;
			for（char?eachChar?:?nfa.getAlphabet（））{
				ArrayList?temp=nullClosure（smove（currenteachChar））;
				boolean?needNew=true;
				for（DFAState?existed?:?states）{
					if（existed.contains（temp））{
						current.connect（existedeachChar）;
						needNew=false;
						break;
					}
				}
				if（needNew?&&?temp.size（）!=0）
				{
					DFAState?newborn=new?DFAState（）;
					newborn.addAll（temp）;
					untagedStates.push（newborn）;
					states.add（newborn）;
					current.connect（newborn?eachChar）;		
				}				
			}
		}
		fillEndStates（）;
	}

	private?ArrayList?smove（DFAState?schar?a）{
		ArrayList?result=new?ArrayList（）;
		for（NFAState?eachState?:?s.getContent（））{
			result.addAll（eachState.move（a））;
		}
		return?result;		
	}

	private?ArrayList?nullCl

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\
?????文件?????????422??2010-06-21?15:49??FundamentalsOfCompiling\.classpath
?????文件?????????607??2010-06-21?14:24??FundamentalsOfCompiling\.project
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\.settings\
?????目錄???????????0??2010-10-17?16:18??FundamentalsOfCompiling\.settings\.svn\
?????文件?????????331??2010-10-17?16:18??FundamentalsOfCompiling\.settings\.svn\entries
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\.settings\.svn\prop-base\
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\.settings\.svn\props\
?????目錄???????????0??2010-10-17?16:18??FundamentalsOfCompiling\.settings\.svn\text-base\
?????文件?????????629??2010-10-17?16:18??FundamentalsOfCompiling\.settings\.svn\text-base\org.eclipse.jdt.core.prefs.svn-base
?????目錄???????????0??2010-10-17?16:18??FundamentalsOfCompiling\.settings\.svn\tmp\
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\.settings\.svn\tmp\prop-base\
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\.settings\.svn\tmp\props\
?????目錄???????????0??2010-10-17?16:18??FundamentalsOfCompiling\.settings\.svn\tmp\text-base\
?????文件?????????629??2010-06-01?19:25??FundamentalsOfCompiling\.settings\org.eclipse.jdt.core.prefs
?????目錄???????????0??2010-10-17?16:18??FundamentalsOfCompiling\.svn\
?????文件?????????668??2010-10-17?16:18??FundamentalsOfCompiling\.svn\entries
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\.svn\prop-base\
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\.svn\props\
?????目錄???????????0??2010-10-17?16:18??FundamentalsOfCompiling\.svn\text-base\
?????文件?????????422??2010-10-17?16:18??FundamentalsOfCompiling\.svn\text-base\.classpath.svn-base
?????文件?????????607??2010-10-17?16:18??FundamentalsOfCompiling\.svn\text-base\.project.svn-base
?????文件????????1295??2010-10-17?16:18??FundamentalsOfCompiling\.svn\text-base\build.xml.svn-base
?????目錄???????????0??2010-10-17?16:18??FundamentalsOfCompiling\.svn\tmp\
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\.svn\tmp\prop-base\
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\.svn\tmp\props\
?????目錄???????????0??2010-10-17?16:18??FundamentalsOfCompiling\.svn\tmp\text-base\
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\bin\
?????目錄???????????0??2010-10-17?16:18??FundamentalsOfCompiling\bin\.svn\
?????文件?????????166??2010-10-17?16:18??FundamentalsOfCompiling\bin\.svn\entries
?????目錄???????????0??2010-10-17?16:17??FundamentalsOfCompiling\bin\.svn\prop-base\
............此處省略247個文件信息