将不确定有穷自动机转化为确定的有穷自动机
题目：将下列的NFA状态图转化为DFA
备注：构造NFA N的子集算法
算法步骤如下：
使用Java代码实现如上算法以及整个流程为：
package com.wcx;
import java.util.*;
/**
* @author ：风雨之都
* @date ：Created 2022/3/15 22:36
*/
public class NFAToDFA {
// 初态节点
private static String startStateNode;
// 终态节点集合
private static ArrayList<String> endStateNodes = new ArrayList<>();
// 标记用户采用的那种方式输入
private static boolean select = true;
// 主函数入口
public static void main(String[] args) {
NFAToDFA nfaToDFA = new NFAToDFA();
nfaToDFA.NFAToDFA();
}
/**
* 将NFA图转化为DFA状态图
*/
private void NFAToDFA(){
selectStartAndEndStateInputWay();
// 获取 NFA(不确定有穷自动机) 的状态图
ArrayList<String> NFA = getNFAStateDiagram();
// 将NFA状态图的集合转化为hashMap存储
HashMap<String, HashMap<String, String>> arrayToHashMapOfNFA = arrayToHashMapOfNFA(NFA);
if(select){
// 获取NFA的初态节点
startStateNode = getStartStateNode(NFA);
if(startStateNode == null){
return;
}
// 获取NFA的终态节点集合
endStateNodes = getEndStateNodes(NFA);
if(endStateNodes.size() == 0){
System.out.println("终态节点识别失败,请检查输入！");
return;
}
}
// 获取NFA的输入字符集合
ArrayList<String> chars = getNFAInputChar(NFA);
// 获取T0~Tn的子集以及DFA的状态图
HashMap<String, Object> nfaSonArray = getNFASonArray(arrayToHashMapOfNFA, startStateNode, chars);
// 获取T0~Tn的子集
ArrayList<ArrayList<String>> tArrays = (ArrayList<ArrayList<String>>)nfaSonArray.get("TArrays");
// 获取DFA的关系状图
ArrayList<String> ttArray = (ArrayList<String>)nfaSonArray.get("TTArray");
// 获取DFA的初态节点
String dfaStartNode = getDFAStartNode(startStateNode, tArrays);
// 获取DFA的终态节点
ArrayList<String> dfaEndNodes = getDFAEndNodes(endStateNodes, tArrays);
// 打印由NFA转化而来的DFA的状态图
printDFA(tArrays,dfaStartNode,dfaEndNodes,ttArray,chars);
}
// 将算出来的DFA的结果打印出来
private void printDFA(ArrayList<ArrayList<String>> tArrays,String dfaStartNode,ArrayList<String> dfaEndNodes,ArrayList<String> ttArray,ArrayList<String> chars){
ArrayList<String> DFA = new ArrayList<>();
System.out.println("NFA的状态K的子集: ");
for (int i = 0; i < tArrays.size(); i++) {
String node = "A" + i + " = " + tArrays.get(i);
DFA.add("[A" + i+"]");
System.out.println(node);
}
System.out.println("(1) DFA的状态集: S = " + DFA);
System.out.println("(2) DFA的字符表：∑ = " + chars);
System.out.println("(3) DFA的转换函数：");
// 将转换函数格式化
for (int i = 0; i < ttArray.size(); i++) {
/*for (int j = 0; j < i + 10; j++) {
ttArray.set(i,ttArray.get(i).replace(j+"","A"+j));
}*/
System.out.println(" "+ttArray.get(i));
}
System.out.println("(4) DFA的初态：S0 = "+DFA.get(Integer.parseInt(dfaStartNode)));
// 经过处理后的终态节点集合
ArrayList<String> dfaEnd = new ArrayList<>();
for (int i = 0; i < dfaEndNodes.size(); i++) {
dfaEnd.add(DFA.get(Integer.parseInt(dfaEndNodes.get(i))));
}
System.out.println("(5) DFA的终态集合：S1 = " + dfaEnd);
}
/**
* 获取DFA的终态节点
* @param endStateNodes NFA的终态节点集合
* @param tArrays T0-T1的子集
* @return 返回终态结果
*/
private ArrayList<String> getDFAEndNodes(ArrayList<String> endStateNodes,ArrayList<ArrayList<String>> tArrays){
// 存放DFA终态节点的下标
ArrayList<String> DFAEndStateNodes = new ArrayList<>();
for (String endStateNode : endStateNodes) {
int count = 0;
for (ArrayList<String> tArray : tArrays) {
// NFA中的终态节点在tArray中找到，表示该集合为DFA的一个终态节点
if (tArray.indexOf(endStateNode) != -1) {
// 判断该终态节点是否已存在，不存在则加入
if (DFAEndStateNodes.indexOf(count+"") == -1) {
DFAEndStateNodes.add(count+"");
}
}
count++;
}
}
return DFAEndStateNodes;
}
/**
* 获取DFA的初态节点
* @param startStateNode NFA的初态节点
* @param tArrays T0-T1的子集
* @return 返回DFA的初态节点
*/
private String getDFAStartNode(String startStateNode,ArrayList<ArrayList<String>> tArrays){
// 待选初态集合
ArrayList<String> startStateNodes = new ArrayList<>();
int count = 0;
for (ArrayList<String> tArray : tArrays) {
// NFA的初态节点在tArray中，表示该集合为DFA的初态
if (tArray.indexOf(startStateNode) != -1) {
// 因为初态节点只会存在一个，所有没有使用indexOf方法，进行判断是否已存在
if(tArray.size() == 1){
return String.valueOf(count);
}
startStateNodes.add(count+"");
}
count++;
}
// 由定理可知，初态节点只可能有一个，如果出现多个，则出入出错
if(startStateNodes.size() != 1){
System.out.println("NFA子集筛选错误或者NFA初态筛选错误！");
return null;
}
// 返回初态节点
return startStateNodes.get(0);
}
/**
* 获取NFA的K的子集
* @param arrayToHashMapOfNFA NFA的状态图转化后hashMap
* @param startStateNode NFA初态节点
* @param chars NFA的输入字符集合
* @return 返回NFA的K的子集
*/
private HashMap<String,Object> getNFASonArray(HashMap<String, HashMap<String, String>> arrayToHashMapOfNFA,String startStateNode,ArrayList<String> chars){
ArrayList<String> array = new ArrayList<>();
array.add(startStateNode);
// 获取初态所映射的空集射弧
array = getEndState(startStateNode, arrayToHashMapOfNFA,array,"c");
// 存放子集T
ArrayList<ArrayList<String>> TArrays = new ArrayList<>();
// 存放DFA状态图
ArrayList<String> TTArray = new ArrayList<>();
// 确定T0
TArrays.add(array);
int count = 0;
// 确定 T1~Tn
do{
array = TArrays.get(count++);
for (String aChar : chars) {
ArrayList<String> a = move(array, aChar, arrayToHashMapOfNFA);
ArrayList<String> b = new ArrayList<>();
for (String s : a) {
b = getEndState(s, arrayToHashMapOfNFA, b, "c");
}
a.addAll(b);
int mark = 0;
for (ArrayList<String> tArray : TArrays) {
if (!equalToArray(tArray,a)) {
mark++;
}else{
TTArray.add("D([A"+(count-1) + "],"+aChar+") = [A" + mark + "]");
}
}
if(mark == TArrays.size()){
if(a.size() != 0){
TArrays.add(a);
}
TTArray.add("D([A"+(count-1) + "],"+aChar+") = [A" + mark + "]");
}
}
}while(count < TArrays.size());
HashMap<String,Object> hashMap = new HashMap<>();
// 存放NFA的子集
hashMap.put("TArrays",orderByAes(TArrays));
// 存放DFA的状态的集合
hashMap.put("TTArray",TTArray);
return hashMap;
}
/**
* 获取NFA的输入字符集合
* @param NFA NFA的状态图
* @return 返回输入字符集合
*/
private ArrayList<String> getNFAInputChar(ArrayList<String> NFA){
ArrayList<String> chars = new ArrayList<>();
for (String s : NFA) {
String[] split = s.split(" ");
// 判断当前输入字母是否表示空集，如不是的话再判断当前输入
if((!"c".equals(split[2]))&&(chars.indexOf(split[2]) == -1)){
chars.add(split[2]);
}
}
return chars;
}
/**
* 获取NFA的初态
* @param NFA NFA状态图
* @return 返回NFA的初态
*/
private String getStartStateNode(ArrayList<String> NFA){
// NFA 的初态集合
ArrayList<String> startNodes = new ArrayList<>();
// NFA的终态集合
ArrayList<String> endNodes = new ArrayList<>();
for (String s : NFA) {
String[] s1 = s.split(" ");
startNodes.add(s1[0]);
endNodes.add(s1[1]);
}
// 如果初态的节点没有在终态的节点集合中，表示该节点为NFA的初态节点
for (String startNode : startNodes) {
if (endNodes.indexOf(startNode) == -1) {
return startNode;
}
}
System.out.println("NFA状态图输入有误，未找到初态节点！");
return null;
}
/**
* 获取NFA的终态集合
* @param NFA NFA状态图
* @return 返回NFA的终态集合
*/
private ArrayList<String> getEndStateNodes(ArrayList<String> NFA){
// NFA 的初态集合
ArrayList<String> startNodes = new ArrayList<>();
// NFA的终态集合
ArrayList<String> endNodes = new ArrayList<>();
// 最终返回的终态集合
ArrayList<String> endStateNodes = new ArrayList<>();
for (String s : NFA) {
String[] s1 = s.split(" ");
startNodes.add(s1[0]);
endNodes.add(s1[1]);
}
// 如果终态节点没有在初态节点中找到，表示该终态节点为NFA的终态节点
for (String endNode : endNodes) {
if (startNodes.indexOf(endNode) == -1) {
endStateNodes.add(endNode);
}
}
return endStateNodes;
}
/**
* 将输入的NFA状态集合转化为HashMap
* @param NFA 需要转换的NFA状态图
* @return 返回转化后的NFA的hasMap状态图
*/
private HashMap<String,HashMap<String,String>> arrayToHashMapOfNFA(ArrayList<String> NFA){
HashMap<String,HashMap<String,String>> hashMap = new HashMap<>();
for (String nfa : NFA) {
// 采用空格分割,分别是初态，终态，关系字母
String[] strings = nfa.split(" ");
// 如果键值对能找到，则表示以string[0] 为键的map存在，则在原有的基础上添加
if (hashMap.get(strings[0]) != null) {
// 两个状态节点可能存在多个关系，使用hasMap时，第一个值会被后面的值覆盖
if(hashMap.get(strings[0]).get(strings[1])==null){
hashMap.get(strings[0]).put(strings[1],strings[2]);
}else{
hashMap.get(strings[0]).put(strings[1],hashMap.get(strings[0]).get(strings[1])+","+strings[2]);
}
}else{ // 找不到键值对，则新建一个
// 存放每两个有关系的状态的信息
HashMap<String,String> map = new HashMap<>();
map.put(strings[1],strings[2]);
hashMap.put(strings[0],map);
}
}
return hashMap;
}
/**
* 获取从键盘输入的NFA状态图
* @return 返回输入的NFA的状态图
*/
private ArrayList<String> getNFAStateDiagram(){
ArrayList<String> NFA = new ArrayList<>();
Scanner scanner = new Scanner(System.in);
System.out.println("请输入NFA状态图关系：");
while (true){
// 输入关系图
String str = scanner.nextLine();
// 以";"结束就结束输入
if(";".equals(str)){
break;
}
NFA.add(str);
}
return NFA;
}
/**
* 集合进行升序排序
* @param arrayLists 将集合中元素进行升序排序
* @return 返回排序后的集合
*/
public ArrayList<ArrayList<String>> orderByAes(ArrayList<ArrayList<String>> arrayLists){
// 遍历获取集合中每个元素
for (ArrayList<String> arrayList : arrayLists) {
try{
ArrayList<Integer> array = new ArrayList<>();
// 如果节点以数字表示，则将字符转化为数字后排序
for (String s : arrayList) {
array.add(Integer.parseInt(s));
}
// 使用Java自带的排序方法
Collections.sort(array);
// 将排序后的数组经过处理放回到原来集合中的位置
for (int i = 0; i < arrayList.size(); i++) {
arrayList.set(i,array.get(i).toString());
}
}catch (Exception e){
// 如果集合中的字符不能转化为数字，及节点不以字符数字表示，不能排序，转换的时候抛出异常，则直接返回该集合
return arrayLists;
}
}
return arrayLists;
}
/**
* 判断非空的两个长度相等的集合是否一样
* @param array1 集合1
* @param array2 集合2
* @return 判断比较结果
*/
public boolean equalToArray(ArrayList<String> array1,ArrayList<String> array2){
// 先判断长度，不等时，直接返回false
if(array1.size() != array2.size()){
return false;
}
// 如果集合长度相等，则依次编译判断是否相等
for (String array : array1) {
boolean mark = false;
for (String s : array2) {
// 只有找到，则退出循环
if (array.equals(s)) {
mark = true;
break;
}
}
// 表示未找到array元素，及两个集合不等，直接返回false
if(!mark){
return false;
}
}
return true;
}
/**
* Move函数
* @param array 需要实现Move的集合
* @param str 需要判断的输入字符
* @param map NFA的状态图
* @return 返回move结果集
*/
private ArrayList<String> move(ArrayList<String> array,String str,HashMap<String,HashMap<String,String>> map){
ArrayList<String> arrayList = new ArrayList<>();
for (String s : array) {
HashMap<String, String> hashMap = map.get(s);
// 为空，表示该节点为终态节点
if(hashMap == null){
continue;
}
Set<String> strings = hashMap.keySet();
for (String string : strings) {
// 两个状态节点存在两个或两个以上的关系，使用,分割
String[] split = hashMap.get(string).split(",");
for (String s1 : split) {
if (s1.equals(str)) {
if(arrayList.indexOf(string) == -1){
arrayList.add(string);
}
}
}
}
}
return arrayList;
}
/**
* 获取node节点后和他相连的空集字符的射弧节点
* @param node 需要处理的节点
* @param map NFA状态图
* @param array 用于存储射弧的节点
* @return 返回最终集合
*/
private ArrayList<String> getEndState(String node,HashMap<String,HashMap<String,String>> map,ArrayList<String> array,String str){
HashMap<String, String> hashMap = map.get(node);
// 为空，表示该节点为终态节点
if(hashMap == null){
return array;
}
Set<String> strings = hashMap.keySet();
for (String string : strings) {
if(hashMap.get(string).equals(str)){
array.add(string);
// 如果该节点后面还有，则递归调用
array = getEndState(string,map,array,str);
}
}
return array;
}
/**
* 选择初态和终态输入方式（自动识别和手动输入）
*/
private void selectStartAndEndStateInputWay(){
Scanner scanner = new Scanner(System.in);
System.out.println("请选择初态和终态确认方式：");
System.out.println("======1、程序自动识别======");
System.out.println("======2、手动录入 ======");
String s = scanner.nextLine();
if("1".equals(s)){
return;
}else if("2".equals(s)){
System.out.print("请输入初态: ");
startStateNode = scanner.nextLine();
System.out.print("请输入终态集合,使用空格隔开：");
String endStates = scanner.nextLine();
endStateNodes.addAll(Arrays.asList(endStates.split(" ")));
select = false;
}else{
selectStartAndEndStateInputWay();
}
}
}
测试输入,以英文输入法的分号（;）表示本次录入结束（因为图的特殊性，输入的时候需要使用如下格式输入，起点(空格)终点(空格)字符） 例如NFA状态图中的第一个关系(0和1的表示方法)为0 1 c c表示图中ε特殊字符，因为在Java输入流中不方便表示，所以使用c来表示，当然也可以使用其他字符表示
运行结果
最终截图图
为便于书写，不妨将【A0】、【A1】、【A2】、【A3】、【A4】重新命名，用0、1、2、3、4分别表示，该DFA M 的状态转换图如图所示。
该方法仅供参考，不是最优结果，如果有需要，可以联系探讨