< DFA M状态最少化的程序实现>编译课程设计啊！！！还要求MFC的界面！！！ 求大神啊！搞定给财富值~

DFA状态数的最小化
package chapter3;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* 算法 3.39 最小化一个DFA的状态数
* @author Administrator
*
*/
publicclass Arithmetic_3_39
{
/**
* 输入一个DFA D
* @param d DFA状态转换表
* @param S 状态集合
* @param E 输入字符表
* @param s 开始状态
* @param F 接受状态集
* @return 一个DFA D', 它和D接受相同的语言, 且输入状态数最少
*/
publicint[][] convert(int[][] d, Set<Integer> S, char[] E, int s, Set<Integer> F)
{
// 首先用接受状态组和非接受状态组划分 PI
Set<Set<Integer>> PI = new HashSet<Set<Integer>>();
// 计算 S - F
S.removeAll(F);
PI.add(F);
PI.add(S);
// 最初, 令PInew = PI
Set<Set<Integer>> PInew = new HashSet<Set<Integer>>();
// TODO 解决浅复制带来的问题
PInew.addAll(PI);
while (true)
{
// 对PI中的每个组G
for (Iterator<Set<Integer>> it = PI.iterator(); it.hasNext(); )
{
List<Object> groupList = new ArrayList<Object>();
Set<Integer> G = it.next();
// 使用字符表测试G的元素
// 对于字符表的每个输入a
for (int i = 0; i < E.length; i++)
{
Map<Integer, Set<Integer>> groupMap = new HashMap<Integer, Set<Integer>>();
char a = E[i];
for (Iterator<Integer> sIt = G.iterator(); sIt.hasNext(); )
{
int stat = sIt.next();
// 从状态S出发 沿着a能够到达的状态
int tar = d[stat][a];
// 获取目标状态在PI中的位置
int idx = getElelementIdx(PI, tar);
Set<Integer> group = groupMap.get(idx);
if (group == null)
{
group = new HashSet<Integer>();
groupMap.put(idx, group);
}
group.add(stat);
}
groupList.add(groupMap);
}
// 在PInew中将G替换为对G进行分组得到的那些小组
PInew.remove(G);
PInew.addAll(setListPoly(groupList));
}
// 判断2个集合组是否相等
if (!isTwoSetGrpEqual(PI, PInew))
{
PI.clear();
PI.addAll(PInew);
} else
{
break;
}
}
// TODO 步骤4
for (Iterator<Set<Integer>> it = PI.iterator(); it.hasNext(); )
{
Set<Integer> set = it.next();
// 令S1是PI组中某个G的代表
for (Iterator<Integer> sIt = set.iterator(); sIt.hasNext(); )
{
int s1 = sIt.next();
while (sIt.hasNext())
{
// 用S1替换SWP
int swp = sIt.next();
for (int i = 0; i < d.length; i++)
{
for (int j = 0; j < d[i].length; j++)
{
if (d[i][j] == swp)
{
d[i][j] = s1;
}
}
}
// 删除SWP的转换函数
d[swp] = newint[]{};
}
}
}
return d;
}
/**
* 获取某个元素在集合组中的索引
* @param set
* @param element
* @return
*/
privateint getElelementIdx(Set<Set<Integer>> set, int element)
{
int idx = 0;
for (Iterator<Set<Integer>> it = set.iterator(); it.hasNext(); )
{
Set<Integer> g = it.next();
if (g.contains(element))
{
// TODO 检查HASHCODE 是否代表了集合的位置
return idx;
}
idx++;
}
return -1;
}
// 计算集合组聚合的结果
@SuppressWarnings("unchecked")
private Set<Set<Integer>> setListPoly(List<Object> oriSetList)
{
Set<Set<Integer>> result = new HashSet<Set<Integer>>();
if (oriSetList.size() > 0)
{
// 读取第一个集合组
Map<Integer, Set<Integer>> groupMap = (Map<Integer, Set<Integer>>)oriSetList.get(0);
for (Iterator<Integer> it = groupMap.keySet().iterator(); it.hasNext(); )
{
result.add(groupMap.get(it.next()));
}
for (int i = 1; i < oriSetList.size(); i++)
{
// 获取中间集合
Map<Integer, Set<Integer>> midMap = (Map<Integer, Set<Integer>>)oriSetList.get(i);
List<Set<Integer>> midSetList = new ArrayList<Set<Integer>>();
for (Iterator<Integer> it = midMap.keySet().iterator(); it.hasNext(); )
{
midSetList.add(midMap.get(it.next()));
}
// 开始计算
// 运算结果
List<Set<Integer>> calcResult = new ArrayList<Set<Integer>>();
for (Iterator<Set<Integer>> it = result.iterator(); it.hasNext(); )
{
Set<Integer> srcSet = it.next();
for (int k = 0; k < midSetList.size(); k++)
{
// 计算2个集合的交集
Set<Integer> mixed = getSetMixed(srcSet, midSetList.get(k));
// 如果结果不为空
if (!mixed.isEmpty())
{
// 保存运算结果
calcResult.add(mixed);
}
}
}
// 将计算结果替换result
result.clear();
result.addAll(calcResult);
}
}
return result;
}
// 计算二个集合的交集
private Set<Integer> getSetMixed(Set<Integer> set1, Set<Integer> set2)
{
Set<Integer> mixed = new HashSet<Integer>();
for (Iterator<Integer> it = set1.iterator(); it.hasNext(); )
{
int emu = it.next();
if (set2.contains(emu))
{
mixed.add(emu);
}
}
return mixed;
}
/**
* 判断2个集合组是否相等
* @param setGrp1
* @param setGrp2
* @return
*/
privateboolean isTwoSetGrpEqual(Set<Set<Integer>> setGrp1, Set<Set<Integer>> setGrp2)
{
boolean same = false;
int matchCounts = 0;
if (setGrp1.size() == setGrp2.size())
{
for (Iterator<Set<Integer>> it = setGrp1.iterator(); it.hasNext(); )
{
Set<Integer> set1 = it.next();
for (Iterator<Set<Integer>> it2 = setGrp2.iterator(); it2.hasNext(); )
{
Set<Integer> set2 = it2.next();
if (set2.equals(set1))
{
matchCounts++;
}
}
}
if (matchCounts == setGrp1.size())
{
same = true;
}
}
return same;
}
}
// 测试:
package test;
import java.util.HashSet;
import java.util.Set;
import chapter3.Arithmetic_3_39;
publicclass TestCase
{
publicstaticvoid main(String[] args)
{
new TestCase().test_339();
}
publicvoid test_339()
{
// DFA的转换表
int[][] d = {{}, {2, 3}, {2, 4}, {2, 3}, {2, 5}, {2, 3}};
// 输入状态集合
Set<Integer> S = new HashSet<Integer>();
S.add(1);
S.add(2);
S.add(3);
S.add(4);
S.add(5);
// 输入字符
char[] E = {0, 1};
int s = 1;
Set<Integer> F = new HashSet<Integer>();
F.add(5);
Arithmetic_3_39 a339 = new Arithmetic_3_39();
a339.convert(d, S, E, s, F);
}
}

对于一个NFA，当把它确定化之后，得到的DFA所具有的状态数可能并不是最小的。其原因之一，就在于上面所给出的确定化算法没有考虑到DFA中具有某种“同一性”的一些状态可加以合并的问题。所谓一个DFA M状态数的最小化，是指构造一个等价的DFA M′，而后者有最小的状态数。为了说明状态数最小化算法的思想，我们先引入可区分状态的概念。设M=(K,Σ,f,S0,Z)为一DFA，并设s和t是M的两个不同状态，我们说状态s,t为某一输入串w所区分，是指从s,t中之一出发，当扫视完w之后到达M的终态，但从其中的另一个状态出发，当扫视完同一个w后而进入非终态。如果两个状态s和t不可区分 (即对任何输入串w，当且仅当f(s,w)∈Z,f(t,w)∈Z)，则称s和t等价。显然，在一个DFA中，就识别符号串的作用而言，相互等价的状态处于同等的地位，故可设法将它们合并，以减少DFA的状态个数。下面给出一个将DFA M状态数最小化的算法。此算法的基本思想，就是将M的状态集K逐步进行划分，以期最后按上述状态的等价关系将K分裂为r个 (r≤|K|)互不相交的子集，使得属于同一子集中的任何两个状态都是等价的，而属于不同子集的任意两个状态都是可区分的。此算法的执行步骤如下：(1) 首先，将M的状态集K按终态与非终态划分为两个子集Z及K-Z，以构成初始分划，记为π={Z,K-Z}。(2) 设当前的分划π中已含有m个子集，即π={I1, I2, …, Im}其中，属于不同子集的状态是可区分的，而属于同一子集中的诸状态则是待区分的。即需对每一子集Ii={Si1,Si2,…,Sin}中各状态Sir (Sir∈K,1≤r≤n)进行考察，看是否还能对它们再进行区分。例如，Sip和Siq是Ii中的两个状态，若有某个a∈Σ，使f(Sip,a)=Sju及f(Siq,a)=Skv，而状态Sju及Skv分别属于π中两个不同的子集Ij和Ik，故Sju与Skv为某一w所区分，从而Sip和Siq必为w所区分，故应将子集Ii进一步细分，使Sip和Siq分别属于Ii的不同的子集。也就是说，对于每一子集Ii及每一a∈Σ，我们需考察Iai=f(Ii,a)=∪n[]r=1f(Sir,a)若Iai中的状态分别落于π中的p个不同的子集，则将Ii分为p个更小的状态子集I(1)i,I(2)i,…，I(p)i，使得对于每一个I(j)i,f(I(j)i,a)中的全部状态都落于π的同一子集之中。注意，若对某状态Sir,f(Sir,a)无意义，则Sir与任何Sit(f(Sit,a)有定义)都是可区分的。这样，每细分一次，就得一个新的分划πnew，且分划中的子集数也由原来的m个变为m+p-1个。(3) 若πnew≠π，则将πnew作为π再重复第2步中的过程，如此等等，直到最后得到一个分划π，使πnew=π，即π中的各个子集不能再细分为止。(4) 对于所得的最后分划π，我们从它的每一子集Ij={Sj1,Sj2,…,Sjr}中任选一个状态，如Sj1，作为Ij中所含各状态的代表，这些所选出的状态便组成了M′的状态集K′。而且，若Ij中含有M的初态，则Sj1为M′的初态；若Ij中含有M的终态，则Sj1为M′的一个终态。此外，为构成DFA M′，还应将各子集中落选的状态从原DFA M中删去，并将原来进入这些状态的所有矢线都改为进入它们的代表状态。例36设已给DFAM=({S0,S1,…,S4}, {a,b},f,S0,{S4})相应的状态转换图和状态转移矩阵如图314(a)及(b)所示。现用上述算法将M最小化。(1) 初始分划由两个子集组成，即π:{S0,S1,S2,S3}, {S4}(2) 为得到下一分划，考察子集{S0,S1,S2,S3}。为叙述方便起见，下面我们用记号{}a表示：当M分别处于该子集各状态之下，对输入符号a转移到的下一状态所组成的集合。因为{S0,S1,S2,S3}a={S1}{S0,S1,S2,S3}但{S0,S1,S2}b={S2,S3}{S3}b={S4}即{S0,S1,S2,S3}b不包含在π的同一子集之中，故应将{S0,S1,S2,S3}分为两个子集{S0,S1,S2}及{S3}，于是便得到下一分划πnew:{S0,S1,S2}, {S3}, {S4}又因πnew≠π，现以πnew作为π，即π:{S0,S1,S2}, {S3}, {S4}再考虑{S0,S1,S2}，因为{S0,S1,S2}a={S1}{S0,S1,S2}而{S0,S2}b={S2}{S1}b={S3}故应将{S0,S1,S2}再分为{S0,S2}及{S1}，从而又得到πnew:{S0,S2}, {S1}, {S3}, {S4}由于此时仍有πnew≠π，故再以πnew作为π，即π:{S0,S2}, {S1}, {S3}, {S4}现考察{S0,S2}，由于{S0,S2}a={S1}而{S0,S2}b={S2}{S0,S2}即{S0,S2}a与{S0,S2}b已分别包含在π的同一子集{S1}及{S0,S2}之中，故子集{S0,S2}已不能再分裂。此时πnew=π，子集分裂的过程宣告结束。(3) 现选择状态S0作为{S0,S2}的代表，将状态S2从状态转换图中删去，并将原来引向S2的矢线都引至S0，这样，我们就得到了化简后的DFA M′，如图315(a)及(b)所示。最后，再考察图314(a)及图315(b)所示的FA。容易看出，它们所接受的语言均是以abb为后缀的任意a,b符号串所组成的集合，也就说，这两个FA是相互等价的。实际上，我们还可以进一步证明如下的定理。定理32对于有同一接受集的FA，与之等价且具有最小状态数的DFA在同构意义下 (即不顾状态的命名)是惟一的。追问

大神。。。不好使诶。。。

追答

根据这个找找思路吧 不要把希望寄托在别人身上啦

温馨提示：答案为网友推荐，仅供参考

当前网址：https://verywind.cn/ee/y72fjjevy.html