DFANFA实现

实现了DFA，NFA算法，DFA最小化，NFA转化为DFA以及正则表达式转化为NFA的算法，是有限状态自动机的初学者很不错的学习资源

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个文件信息