package?dfa;

import?java.io.*;
import?java.util.*;

import?fa.*;

public?class?DFA?extends?FA?{	
	//開始狀態
	protected?FAState?startState;

	public?DFA（）?{		
	}
	
	/**
	?*?構造函數
	?*?@param?filePath?包含有限狀態自動機的構造所需的數據的文件的路徑
	?*?		文件的格式舉例如下:
	?*?					?5?3
?????????????????????????1?2?3?4?5
?????????????????????????b?a?!
?????????????????????????1
?????????????????????????5
?????????????????????????1?-1?-1
?????????????????????????-1?2?-1
?????????????????????????-1?3?-1
?????????????????????????-1?3?4
?????????????????????????-1?-1?-1
	??????其中，第一行的兩個數字分別表示?自動機狀態的數目和符號串的數目
			第二行的數字為每一個狀態的id
			第三行為符號串（符號串間以空格隔開）
			第四行的數字為開始狀態的id
			第五行的數字為結束狀態的id
			最后幾行為狀態轉換矩陣		
	?*/
	public?DFA（String?filePath）?{
		super（filePath）;	?
	}

	public?DFA（FAState?startState?List?acceptingStates
			List?states?List?alphabet?
			List>?stateTransitionMat）?{
		this.startState?=?startState;
		this.acceptingStates?=?acceptingStates;
		this.states?=?states;
		this.alphabet?=?alphabet;
		this.stateTransitionMat?=?stateTransitionMat;
	}
	
	//從文件中解析狀態轉移矩陣
	public?void?getStateTransitionsFromFile（BufferedReader?in?int?statesNum?int?alphaNum）?
			throws?IOException?{
		this.stateTransitionMat?=?new?ArrayList>（）;
		for（int?i=0;?i			stateTransitionMat.add（new?ArrayList（））;
			
			String?rowOfTransit?=?in.readLine（）;
			String[]?transitions?=?rowOfTransit.trim（）.split（“?“）;				
			for（int?j=0;?j				//構造搜索節點
				int?stateIndex?=?Integer.parseInt（transitions[j]）;
				TransitMatElement?transitEle?=?
						new?TransitMatElement（j?stateIndex）;
				stateTransitionMat.get（i）.add（transitEle）;
			}
		}
	}

	/**
	?*?使用自動機識別符號串
	?*?@param?words?待匹配符號串
	?*?@return?如果接受，則返回true否則，返回false?
	?*/
	public?boolean?recognize（String[]?words）?{
		FAState?currentState?=?this.startState;
		int?countOfWordsRecognized?=?0;
		while（countOfWordsRecognized?<=?words.length）?{
			if（isAccepted（currentState?countOfWordsRecognized?words.length））?{??//接收
				return?true;
			}?else?if（wordsTerminatedButNotAccepted（currentState?words.length
					countOfWordsRecognized））?{
				return?false;
			}				
			//?當前待識別的單詞在alphabet中的下標
			int?indexOfAlpha?=?alphabet.indexOf（words[countOfWordsRecognized]）;
			//查找狀態轉移矩陣，獲取將要跳轉到的狀態的下標
			int?transition?=?
					getIndexOfStateToSwitch（states.indexOf（currentState）?indexOfAlpha）;
			if（transition?==?-1）?{			//不能匹配當前符號串，拒絕
				return?false;
			}?else?{
				currentState?=?this.states.get（transition）;???//進行下一個符號串的接收				
				countOfWordsRecognized++;								
			}								
		}		
		return?false;
	}
	
	//判斷字符串是否已經被識別
	protected?boolean?isAccepted（FAState?state?int?countOfWordsRecognized?int?wordsArrLength）?{
		return?countOfWordsRecognized?==?wordsArrLength?&&?acceptingStates.contains（state）;		
	}
	
	//?輸入的符號串已經識別完畢，但還未遇到接收狀態
	protected?boolean?w

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????379??2014-02-26?16:57??FSA\.classpath

?????文件????????379??2014-02-26?14:09??FSA\.project

?????文件????????598??2014-02-26?14:09??FSA\.settings\org.eclipse.jdt.core.prefs

?????文件???????9311??2014-03-24?22:10??FSA\bin\dfa\DFA.class

?????文件???????1400??2014-03-24?13:59??FSA\bin\dfa\DFATest.class

?????文件???????5694??2014-03-24?21:40??FSA\bin\fa\FA.class

?????文件???????1871??2014-03-24?13:59??FSA\bin\fa\FAState.class

?????文件????????558??2014-03-24?13:59??FSA\bin\fa\TransitMatElement.class

?????文件??????12681??2014-03-24?13:59??FSA\bin\nfa\NFA.class

?????文件???????9135??2014-03-24?13:59??FSA\bin\nfa\NFA2DFA.class

?????文件???????2286??2014-03-24?13:59??FSA\bin\nfa\NFATest.class

?????文件???????4142??2014-03-24?13:59??FSA\bin\regexp2nfa\Regexp.class

?????文件????????998??2014-03-24?13:59??FSA\bin\regexp2nfa\RegexpTest.class

?????文件?????????72??2014-02-26?21:16??FSA\dfa_1.txt

?????文件?????????89??2014-02-27?16:58??FSA\nfa_1.txt

?????文件?????????77??2014-03-02?01:03??FSA\nfa_2.txt

?????文件?????????87??2014-03-02?14:06??FSA\nfa_3.txt

?????文件?????????49??2014-03-16?20:48??FSA\nfa_for_closure.txt

?????文件?????????30??2014-03-16?18:51??FSA\nfa_for_concatenation_1.txt

?????文件?????????30??2014-03-16?18:52??FSA\nfa_for_concatenation_2.txt

?????文件?????????30??2014-03-16?22:59??FSA\nfa_for_union_1.txt

?????文件?????????30??2014-03-16?23:49??FSA\nfa_for_union_2.txt

?????文件??????11843??2014-03-24?22:10??FSA\src\dfa\DFA.java

?????文件???????1470??2014-03-18?20:37??FSA\src\dfa\DFATest.java

?????文件???????5058??2014-03-24?21:40??FSA\src\fa\FA.java

?????文件???????1160??2014-03-15?21:21??FSA\src\fa\FAState.java

?????文件????????467??2014-02-28?21:09??FSA\src\fa\TransitMatElement.java

?????文件??????18786??2014-03-18?12:22??FSA\src\nfa\NFA.java

?????文件???????9485??2014-03-18?12:16??FSA\src\nfa\NFA2DFA.java

?????文件???????3351??2014-03-18?12:16??FSA\src\nfa\NFATest.java

............此處省略17個文件信息