首页 > 代码库 > NFA->DFA->最简DFA
NFA->DFA->最简DFA
/**
*author Young
*
*2014-5-11
*
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class NFAtoDFA {
static String map[][];
static int endNum;
//保存所有状态
static ArrayList<Set<Integer>>list=new ArrayList<Set<Integer>>();
//输入符号列
static ArrayList<String>operatorList=new ArrayList<String>();
//fromSetToSet中每个元素对应 list中从哪个状态下标到哪个状态下表经过的符号及对应下标
static ArrayList<SetOperatorSet>fromSetToSet=new ArrayList<SetOperatorSet>();
static Scanner sc=new Scanner(System.in);
public static void main(String[] args) {
System.out.println("输入终结符号（最大值）");
//默认最大值是终结 0是开始
endNum=sc.nextInt();
map=new String[endNum+1][endNum+1];
initMap();
System.out.println("输入符号集（空格分隔，e代表可自动到达）");
sc.nextLine();
String line=sc.nextLine();
for(String str:line.split(" +"))
{
operatorList.add(str);
}
System.out.println();
int s,e;
String operator;
//-1表示输入结束
while(sc.hasNext())
{
s=sc.nextInt();
if(s==-1)
break;
operator=sc.next();
e=sc.nextInt();
map[s][e]=operator;
}
//把第一个状态加入list
list.add(getSetStartWith(0));
for(int i=0;i<list.size();i++)
{
Set<Integer> set=list.get(i);
//======把符号作用于集合=======
for(String ope:operatorList)
{
if(ope.equals("e"))
continue;
Iterator<Integer> iter=set.iterator();
//set2 保存从某一集合（list中）经过某一符号达到的所有集合组成的集合
Set<Integer> set2=new TreeSet<Integer>();
//依次把该符号作用于该集合的每一个数字
while(iter.hasNext())
{
//每次获取该集合中一个数字
int fromNum=iter.next();
//获取从该数字经过ope到达的数字 -1表示不达到
int toNum=getIndexFromWithOperatorTo(fromNum,ope);
if(toNum==-1)
continue;
//获取从toNum开始的可自动到达的集合,并加入set2
set2.addAll(getSetStartWith(toNum));
}
//若list中存在该状态集合
if(list.contains(set2))
{
//找到list中该状态集合下标
int index=list.indexOf(set2);
//结果列表中添加由list中第i个状态经ope达到list中第index个状态
fromSetToSet.add(new SetOperatorSet(i, index, ope));
}
else
{
if(set2.size()!=0)
{
//若list中原本没有改状态，则把新状态加入list，并把list中第i个状态经ope达到list中最后一个状态
list.add(set2);
fromSetToSet.add(new SetOperatorSet(i, list.size()-1, ope));
}
}
}
//======把符号作用于集合结束=======
}
showResult();
////////////===============NFA 化 DFA 结束 ======================///////////////
///==================化简 DFA=======================/////
new SimpleDFA( endNum, list, operatorList, fromSetToSet).start();
}
private static void initMap() {
for(int i=0;i<endNum+1;i++)
for(int j=0;j<endNum+1;j++)
map[i][j]="";
}
private static void showResult() {
for(int i=0;i<list.size();i++)
{
System.out.println(i+1+" "+list.get(i));
}
Collections.sort(fromSetToSet);
System.out.println("\n\n");
for(SetOperatorSet li:fromSetToSet)
{
System.out.println(li.fromListIndex+1+" "+li.operator+" "+(li.toListIndex+1));
}
System.out.println("\n\n==========\n");
}
//获取map中从fromNum经过ope到达的数字 -1表示无法达到
private static int getIndexFromWithOperatorTo(int fromNum, String ope) {
for(int i=0;i<endNum+1;i++)
{
if(map[fromNum][i].equals(ope))
return i;
}
return -1;
}
//获取从s开始可自动达到的集合
private static Set<Integer> getSetStartWith(int s) {
Set<Integer> set=new TreeSet<Integer>();
set.add(s);
DFS(s,set);
return set;
}
//搜索从s开始可自动达到的集合
private static void DFS(int s,Set<Integer> set) {
for(int i=0;i<=endNum;i++)
{
if(map[s][i].equals("e")&&!set.contains(i))
{
set.add(i);
DFS(i,set);
}
}
}
}
class SetOperatorSet implements Comparable<SetOperatorSet>{
public int fromListIndex;
public int toListIndex;
public String operator;
public SetOperatorSet(int fromListIndex, int toListIndex, String operator) {
this.fromListIndex = fromListIndex;
this.toListIndex = toListIndex;
this.operator = operator;
}
@Override
public boolean equals(Object obj) {
SetOperatorSet sos=(SetOperatorSet)obj;
if(this.fromListIndex==sos.fromListIndex&&this.toListIndex==sos.toListIndex&&this.operator.equals(sos.operator))
return true;
return false;
}
@Override
public int compareTo(SetOperatorSet o) {
// return this.operator.compareTo(o.operator);
// if(this.fromListIndex==o.fromListIndex&&this.toListIndex==o.toListIndex&&this.operator.equals(o.operator))
// return 0;
return this.fromListIndex-o.fromListIndex;
}
@Override
public String toString() {
return fromListIndex+ " "+operator+" "+toListIndex;
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class SimpleDFA {
int endNum;
//保存所有状态
ArrayList<Set<Integer>>list;
//输入符号列
ArrayList<String>operatorList;
//fromSetToSet中每个元素对应 list中从哪个状态下标到哪个状态下表经过的符号及对应下标
ArrayList<SetOperatorSet>fromSetToSet;
ArrayList<Set<Integer>>result=new ArrayList<Set<Integer>>();
ArrayList<Set<Integer>>tempList=new ArrayList<Set<Integer>>();
public SimpleDFA(int endNum, ArrayList<Set<Integer>> list,ArrayList<String> operatorList,ArrayList<SetOperatorSet> fromSetToSet) {
this.endNum = endNum;
this.list = list;
this.operatorList = operatorList;
this.fromSetToSet = fromSetToSet;
}
public void start() {
DividedSetByEndNum();
for(int i=0;i<tempList.size();i++)
{
Set<Integer>set=tempList.get(i);
int j;
for( j=0;j<operatorList.size();j++)
{
if(operatorList.get(j).equals("e"))
continue;
if(needDivided(i,set,operatorList.get(j)))
{
break;
}
}
if(j>=operatorList.size())
{
result.add(set);
}
}
showResult();
}
private void showResult() {
System.out.println("\n\n========最简化DFA===\n");
for(int i=0;i<result.size();i++)
{
System.out.println( result.get(i));
}
for(int i=0;i<result.size();i++)
{
Set<Integer>set=result.get(i);
if(set.size()==1)
continue;
Iterator<Integer>itr=set.iterator();
int firstInSet=itr.next()-1;
while(itr.hasNext())
{
int next=itr.next()-1;
for(int j=0;j<fromSetToSet.size();j++)
{
SetOperatorSet sos=fromSetToSet.get(j);
if(sos.fromListIndex==next)
{
sos.fromListIndex=firstInSet;
}
if(sos.toListIndex==next)
{
sos.toListIndex=firstInSet;
}
}
}
}
// System.out.println("\n替换完毕\n");
// for(int j=0;j<fromSetToSet.size();j++)
// {
// SetOperatorSet li=fromSetToSet.get(j);
// System.out.println(li.fromListIndex+" "+li.operator+" "+(li.toListIndex));
// }
ArrayList<SetOperatorSet>sosSet=new ArrayList<SetOperatorSet>();
for(SetOperatorSet sos:fromSetToSet)
{
// System.out.print(sos);
if(!sosSet.contains(sos))
sosSet.add(sos);
}
System.out.println("========最终结果=========");
for(SetOperatorSet sos:sosSet)
{
System.out.println(sos.fromListIndex+1+" "+sos.operator+" "+(1+sos.toListIndex));
}
}
private boolean needDivided(int i,Set<Integer> set, String ope2) {
Set<Integer>set2=new TreeSet<Integer>();
Map<Integer,Set<Integer>>map=new HashMap<Integer,Set<Integer>>();
Iterator<Integer>itr=set.iterator();
while(itr.hasNext())
{
int fromStatue=itr.next();
int toStatue=getFromByOperatorTo( fromStatue, ope2);
if(toStatue==-1)
continue;
int aimStatuIndex=getAimStatuIndexByReaultAndTempList(i,toStatue);
if(set2.add(aimStatuIndex))
{
Set<Integer> set3=new TreeSet<Integer>();
set3.add(fromStatue);
map.put(aimStatuIndex, set3);
}
else
{
Set<Integer> set3=map.get(aimStatuIndex);
set3.add(fromStatue);
}
}
if(set2.size()<=1)
{
return false;
}
Iterator<Integer>iterator=set2.iterator();
while(iterator.hasNext())
{
int index=iterator.next();
Set<Integer> s=map.get(index);
if(s.size()==1)
{
result.add(s);
}
else
{
tempList.add(s);
}
}
return true;
}
private int getAimStatuIndexByReaultAndTempList(int i,int toStatue) {
for(;i<tempList.size();i++)
{
Set<Integer>set=tempList.get(i);
if(set.contains(toStatue))
return i;
}
for(int j=0;j<result.size();j++)
{
Set<Integer>set=result.get(j);
if(set.contains(toStatue))
return -j-1;
}
return Integer.MAX_VALUE;
}
private void DividedSetByEndNum() {
Set<Integer>endSet=new TreeSet<Integer>();
Set<Integer>unEndSet=new TreeSet<Integer>();
for(int i=0;i<list.size();i++)
{
Set<Integer>s=list.get(i);
if(s.contains(endNum))
{
endSet.add(i+1);
}
else
unEndSet.add(i+1);
}
tempList.add(unEndSet);
tempList.add(endSet);
}
private int getFromByOperatorTo(int sStatu, String ope) {
for(int i=0;i<fromSetToSet.size();i++)
{
SetOperatorSet sos=fromSetToSet.get(i);
if(sos.fromListIndex+1==sStatu&&sos.operator.equals(ope))
return sos.toListIndex+1;
}
return -1;
}
}
/*
测试样例
10
e a b
0 e 1
0 e 7
1 e 2
1 e 4
2 a 3
4 b 5
3 e 6
5 e 6
6 e 1
6 e 7
7 a 8
8 b 9
9 b 10
-1
==================
1 [0, 1, 2, 4, 7]
2 [1, 2, 3, 4, 6, 7, 8]
3 [1, 2, 4, 5, 6, 7]
4 [1, 2, 4, 5, 6, 7, 9]
5 [1, 2, 4, 5, 6, 7, 10]
1 a 2
1 b 3
2 a 2
2 b 4
3 a 2
3 b 3
4 a 2
4 b 5
5 a 2
5 b 3
==========
========最简化DFA===
[4]
[5]
[2]
[1, 3]
==========
========最终结果=========
1 a 2
1 b 1
2 a 2
2 b 4
4 a 2
4 b 5
5 a 2
5 b 1
==================
测试样例
13
e a b
0 e 1
0 e 3
1 b 2
2 e 1
2 e 3
3 a 4
4 b 5
5 e 6
6 e 13
6 e 7
6 e 9
7 b 8
8 e 12
9 a 10
10 b 11
11 e 12
12 e 13
12 e 6
-1
=====================
1 [0, 1, 3]
2 [4]
3 [1, 2, 3]
4 [5, 6, 7, 9, 13]
5 [10]
6 [6, 7, 8, 9, 12, 13]
7 [6, 7, 9, 11, 12, 13]
1 a 2
1 b 3
2 b 4
3 a 2
3 b 3
4 a 5
4 b 6
5 b 7
6 a 5
6 b 6
7 a 5
7 b 6
==========
========最简化DFA===
[4, 6, 7]
[1, 3]
[2, 5]
==========
========最终结果=========
1 a 2
1 b 1
2 b 4
4 a 2
4 b 4
*/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。