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

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 = 0i <E.lengthi++)

{

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 = 0i <d.lengthi++)

{

for (int j = 0j <d[i].lengthj++)

{

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 = 1i <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 = 0k <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在同构意义下 (即不顾状态的命名)是惟一的。

1.任何DFA都不能蚂大识别e(空)符号串

2.一个DFA,只能包含唯一的开始状誉物锋态3.DFA识别的符号串集合,可以庆晌是有限的

4.一个DFA,所有的映射必须是单值...