第05章正则语言的性质-28、29、30节课-2013-11-12

研究动机{0n1n|n

1}不是RL。不具有RL的性质，因此不存在RG，FA，RE等的形式描述。RL有什么性质？对给定的RL，能否/如何找到最小的DFA？？第5章正则语言的性质5.1正则语言的泵引理5.2正则语言的封闭性5.3Myhill-Nerode定理与DFA的极小化5.4关于正则语言的判断算法5.5小结第5章

正则语言的性质RL性质泵引理及其应用

并、乘积、闭包、补、交、正则代换、同态、逆同态的封闭性

从RL固有特征寻求表示的一致性Myhill-Nerode定理FA的极小化

RL的几个判定问题空否、有穷否、两个DFA等价否、成员关系

5.1正则语言的泵引理任何有穷语言都是RL逆否命题：非RL一定是无穷语言问题：无穷语言是否一定不是RL？？？解决方案：从RL的“本质”特征出发5.1正则语言的泵引理DFA是RL的识别模型。一个DFA只有有穷个状态，当该DFA识别的语言L是无穷语言时，L中必定存在一个足够长(大于DFA的可达状态数)的句子，使得DFA在识别该句子的过程中，肯定要重复地经过某一状态。5.1正则语言的泵引理如句子z=a1a2…

am

，假设DFAM在识别它的过程中经过的状态依次为q0q1…

qm，根据鸽笼原理，则当m大于M的可达状态数时，这些状态至少有一对是重复的，不妨令为qk和qj，显然kj。泵引理推导示意图Sa1q0q1qka2…akak+1…ajqjaj+1…amqmSa1q0q1qk=qja2…akak+1…ajaj+1…amqm泵引理证明设L是一个RL，DFAM=(Q,,,q0,F)满足L(M)=L，|Q|=N，并假设M中不含任何不可达状态。取L的句子z=a1a2…am(m

N)对h

[1..m]，令(q0,a1a2…ah)=qh由于m

N

，所以k,j[0..N],k

<j且qk=qj泵引理证明(续)此时有(q0,a1a2…ak)=qk(qk,ak+1…aj)=qj=qk(qj,aj+1…am)=qm所以对于非负整数i(qk,(ak+1…aj)i)=(qk,(ak+1…aj)i-1)=…=(qk,ak+1…aj)=qkSa1q0q1qka2…akak+1…ajqjaj+1…amqm泵引理证明(续)因为zL(M)，所以qmF而(q0,a1a2…ak(ak+1…aj)iaj+1…am)=qmF所以a1a2…ak(ak+1…aj)iaj+1…amL(M)

取u=a1a2…akv=ak+1…ajw=aj+1…am有：对非负整数i,uviwL注意到j

N,k<j,有：|uv|

N,|v|1Sa1q0q1qka2…akak+1…ajqjaj+1…amqm引理5-1设L为一个RL，则存在仅依赖于L的正整数N，对于zL，如果|z|N，则u，v，w，st.(1)z=uvw(2)|uv|N(3)|v|1(4)对于整数i0，uviwL(5)N不大于接受L的最小DFAM的状态数例5-1证明{0n1n|n1}不是RL。证明：令L={0n1n|n1}

。假设L是RL，则它满足泵引理。不妨设N是泵引理中仅依赖于L的正整数，取

z

=

0N1N，显然zL此时必然u,v,wst.z=uvw,|uv|N,

|v|1，因此v只可能是由0组成的非空串设v=0k，

k1

;w=0j1N则u=0N-k-j例5-1(续)从而有

uviw=0N-k-j(0k)i0j1N

当i=2时，uv2w=0N-k-j02k0j1N=0N+k1N由于k1，N+k>N

也就是说，uv2w

L，这与泵引理矛盾。所以，L不是RL。例5-2例5-2证明{0n|n为素数}不是RL。证明：假设L={0n|n为素数}是RL。取z=0N+p∈L，不妨设v=0k， k≥1，w=0j

从而有，

uviw=0N+p-k-j(0k)i0j

=0N+p+(i-1)k例5-2（续）当i=N+p+1时，

N+p+(i-1)k=N+p+(N+p+1-1)k =N+p+(N+p)k =(N+p)(1+k)注意到k≥1，所以

N+p+(N+p+1-1)k=(N+p)(1+k)不是素数。故当i=N+p+1时，uvN+p+1w=0(N+p)(1+k)

L这与泵引理矛盾。所以，L不是RL。例5-3证明{0n1m2n+m|m,n1}不是RL。证明：令L={0n1m2n+m|m,n1}

。假设L是RL，则它满足泵引理。不妨设N是泵引理中仅依赖于L的正整数，取

z

=

0N1N22N，显然zL此时必然u,v,wst.z=uvw,|uv|N,

|v|1，因此v只可能是由0组成的非空串设v=0k，

k1

;w=0j1N22N则u=0N-k-j例5-3(续)从而有

uviw=0N-k-j(0k)i0j1N22N

当i=0时，uv0w=0N-k1N22N由于k1，N–k+N<2N

也就是说，uv0wL，这与泵引理矛盾。所以，L不是RL。例5-3(续)注意：本例与例5-1非常相似。实际上，证明一个语言不是RL的题都需要相同的步骤（模板）。虽然取z

=

0N1N22N，但当0串被泵进/泵出时，应说明它不满足0n1m2n+m，而不是0n1n22n。泵引理的注意事项用来证明一个语言不是RL不能用泵引理去证明一个语言是RL。

(1)由于泵引理给出的是RL的必要条件，所以，在用它证明一个语言不是RL时，我们使用反证法。(2)由于泵引理指出，如果L是RL，则对任意的z∈L，只要|z|≥N，一定会存在u、v、w，使uviw∈L对所有的i成立。因此，我们在选择z时，就需要注意到论证时的简洁和方便。(3)当一个特意被选来用作“发现矛盾”的z确定以后，就必须依照|uv|≤N和|v|≥1的要求，说明v不存在(对“存在u、v、w”的否定)。作业(见习题)2.(1)(3)(8)5.2正则语言的封闭性定义5-1

如果任意的、属于某一语言类的语言在某一特定运算下所得的结果仍然是该类语言，则称该语言类对此运算是封闭的，并称该语言类对此运算具有封闭性(closureproperty)。我们所熟悉的封闭性：整数对于加法是封闭的，有理数对于乘法/除法是封闭的。有效封闭性给定一个语言类的若干个语言的描述。如果存在一个算法，它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述，则称此语言类对相应的运算是有效封闭的，并称此语言类对相应的运算具有有效封闭性(validclosureproperty)。定理5-1RL在并、乘积、闭包运算下是封闭的。根据RE的定义，立即可以得到此定理。定理5-2RL在补运算下是封闭的。补：两个DFA具有互补的终止状态。如果DFAM=(Q,,,q0,F)识别的语言为L，那么DFAM'=(Q,,,q0,Q–F)识别的语言应为*–L。定理5-2（续）RL在补运算下是封闭的。证明：(补：两个DFA具有互补的终止状态。)M=(Q，∑，δ，q0，F)，L(M)=L，取DFAM′=(Q，∑，δ，q0，Q-F)

显然，对于任意的x∈∑*，

δ(q0，x)=f∈Fδ(q0，x)=fQ-F

即：x∈L(M)xL(M′)，

L(M′)=∑*-L(M)。所以，RL在补运算下是封闭的。定理得到证明。定理5-3RL在交运算下是封闭的。交：同时满足两个RL。证明：由定理5-1（RL在并、乘积、闭包运算下是封闭的），定理5-2（RL在补运算下是封闭的）及DeMorgan定理可得。定义5-2设,

是两个字母表，映射f:2*称为是从到的代换(substitution)。如果对于a

，f(a)是上的RL，则称f为正则代换(regularsubstitution)。复习：*是指字母表上的克林闭包，即中若干个字符连接而成字符串的集合(P30)；而2*是指*的幂集(P10)扩展先将f的定义域扩展到*上：f:*2*(1)f()={}(允许空字符)(2)f(xa)=f(x)f(a)(允许字符串)再将f的定义域扩展到2*上：f:2*2*对于L*，

f(L)=f(x)(允许字符串集合，即语言)例5-4设

={0,1},={a,b},f(0)=a,f(1)=b*，(注意没有严格区分a与{a},b*本身是一个正则表达式，它表示了一个集合)则f(010)=f(0)f(1)f(0)=ab*a

f({11,00})=f(11)f(00)=f(1)f(1)f(0)f(0)=b*b*

+aa=b*

+aa定义5-3设,

是两个字母表，映射f:2*为正则代换，则(1)f(Ø)=Ø(2)f()=

(3)对于a，f(a)

是上的正则表达式(4)如果r,s是上的正则表达式，则f(r+s)=f(r)+f(s)f(rs)=f(s)f(s)f(r*)=f(r)*是上的正则表达式定理5-4设L是上的一个RL,

f:2*为正则代换，则f(L)也是RL。证明过程：根据定义5-2（正则代换），定义5-3（正则表达式）及定义4-1（正则表达式），利用数学归纳法。定理5-4（续）设L是∑上的一个

RL

是正则代换，则f(L)也是

RL。证明：描述工具：RE。对r中运算符的个数n施以归纳，证明f(r)是表示f(L)的RE。定理5-4（续）当n=0时，结论成立。当n≤k时定理成立,即当r中运算符的个数不大于k时：f(L(r))=L(f(r))。当n=k+1时，定理5-4（续）⑴r=r1+r2。

f(L)=f(L(r))=f(L(r1+r2))=f(L(r1)∪L(r2)) RE的定义

=f(L(r1))∪f(L(r2)) 正则代换的定义

=L(f(r1))∪L(f(r2)) 归纳假设

=L(f(r1)+f(r2)) RE的定义

=L(f(r1+r2)) RE的正则代换的定义

=L(f(r))定理5-4（续）⑵r=r1r2。

f(L)=f(L(r))=f(L(r1r2))=f(L(r1)L(r2)) RE的定义

=f(L(r1))f(L(r2)) 正则代换的定义

=L(f(r1))L(f(r2)) 归纳假设

=L(f(r1)f(r2)) RE的定义

=L(f(r1r2)) RE的正则代换的定义

=L(f(r))定理5-4（续）⑶r=r1*。

f(L)=f(L(r))=f(L(r1*))=f(L(r1)*) RE的定义

=(f(L(r1)))*

正则代换的定义

=(L(f(r1)))*

归纳假设

=L(f(r1)*) RE的定义

=L(f(r1*)) RE的正则代换的定义

=L(f(r))例5-4设

={0,1},={a,b},f(0)=a,f(1)=b*，(注意没有严格区分a与{a},b*本身是一个正则表达式，它表示了一个集合)则f(L(0*(0+1)1*)=L(a*(a+b*)b*)

=L(a*ab*+a*b*b*)=L(a*b*)例5-5设

={0,1,2},={a,b},f(0)=ab,f(1)=b*a*,f(2)=a*(a+b)，则f(010)=abb*a*ab=ab+a+b

f((0+1+2)*)

=

(ab+b*a*+a*(a+b))*=

(ab+b*a*+a++a*b)*f(0(0+1+2)*)

=ab(a+b)*f(012)

=abb*a*a*(a+b)

=ab+a*(a+b)定义5-4设,

是两个字母表，f:

*为映射。如果对于x,y*，f(xy)=f(x)f(y)则称f

为从到*的同态映射(homomorhism)。对于L

*，L的同态像f(L)=f(x)定义5-4(续)对于w

*，w的同态原像是一个集合f-1(w)={x|f(x)=w且x*}对于L

*，L的同态原像是一个集合f-1(L)={x|f(x)L}例5-6设

={0,1},={a,b},f(0)=aa,f(1)=aba,则f(01)=aaaba

f((01)*)=(aaaba)*f-1(aab)=Øf-1({aaa,aba,abaaaaa,abaaaaaa})={1,100}f-1((ab+ba)*a)={1}f(f-1((ab+ba)*a))={aba}f(f-1(L))=L？？？？注意同态映射是正则代换的特例原因：比较其值域可知正则代换的值域为2*同态映射的值域为*推论5-1RL的同态像是RL。证明：注意到同态映射是正则代换的特例，可以直接得到此结论。此推论表明，

RL在同态映射下是封闭的。定理5-5RL的同态原像是RL。构造，证明(略)。定义5-5设L1,L2

*，L2除以L1的商（quotient）定义为L1/L2

={x|yL2st.xyL1}对商的计算：考虑句子的后缀例5-7考虑

{0,1}上的如下语言设L1=01,L2=01,

则L1/L2={}设L1=(01)*,L2=(01)*,则L1/L2=L1设L1=0*011*,L2=00,则L1/L2=Ø设L1=00*1*1,L2=00*1*1,则L1/L2=0*练习设L1={000},L2={},

L3={，0},L4={，0,00},L5={，0,00,000},则L1/L2=L1/L3=L1/L4=L1/L5={000}，{000，00}，{000，00,0}，

{000，00,0，}定理5-6

设L1、L2∑*，如果L1是

RL，则L1/L2也是

RL。证明：设L1

∑*是

RL，

DFAM=(Q，∑，δ，q0，F)，L(M)=L1DFAM′=(Q，∑，δ，q0，F′)F′={q|y∈L2，δ(q，y)∈F}显然，

L(M′)=L1/L2。定理得证。

定理5-6（续）注意L2可以是任意语言，所以这种封闭性不是有效封闭性。5.3Myhill-Nerode定理与DFA的极小化2023/2/3515.3.1Myhill-Nerode定理定义5-6DFAM确定的等价关系。

M=(Q，∑，δ，q0，F)，对于x，y∈∑*xRMyδ(q0，x)=δ(q0，y)。显然，xRMy

q∈Q，x，y∈set(q)

2023/2/3525.3.1Myhill-Nerode定理例5-8设

L=0*10*，它对应的DFAM如下图。2023/2/3535.3.1Myhill-Nerode定理对应于q0：(00)nRM(00)m n，m≥0；对应于q1：0(00)nRM0(00)m n，m≥0；对应于q2：(00)n1

RM(00)m1 n，m≥0；对应于q3：0(00)n1RM0(00)m1 n，m≥0；对应于q4：0(00)n10kRM0(00)m10h

n，m≥0,k,h≥1；

(00)n10kRM(00)m10h n,m≥0，k,h≥1；

0(00)n10kRM(00)m10h n,m≥0，k,h≥1；也就是：

0n10kRM0m10h n,m≥0，k,h≥1；对应于q5：xRMy——x，y为至少含两个1的串。

2023/2/3545.3.1Myhill-Nerode定理定义5-7L确定的∑*上的关系RL。

对于x，y∈∑*，

xRLy(对z∈∑*，xz∈Lyz∈L)

对于x，y∈∑*，如果xRLy，则在x和y后无论接∑*中的任何串z，xz和yz要么都是L的句子，要么都不是L的句子。

2023/2/3555.3.1Myhill-Nerode定理任意x，y∈set(q)，δ(q0，x)=δ(q0，y)=q对于z∈∑*，δ(q0，xz)=δ(δ(q0，x)，z))=δ(q，z)=δ(δ(q0，y)，z)=δ(q0，yz)这就是说，δ(q0，xz)∈Fδ(q0，yz)∈F2023/2/3565.3.1Myhill-Nerode定理即，对于z∈∑*，

xz∈Lyz∈L。表明，

xRLy，也就是xRL(M)y。2023/2/3575.3.1Myhill-Nerode定理定义5-8右不变的(rightlnvariant)等价关系

设R是∑*上的等价关系，对于x，y∈∑*，如果xRLy，则必有xzRLyz，对于z∈∑*成立，则称R是右不变的等价关系。2023/2/3585.3.1Myhill-Nerode定理命题5-1

对任意DFAM=(Q，∑，δ，q0，F)，M确定的∑*上的关系RM为右不变的等价关系证明：⑴RM是等价关系。自反性显然。对称性：x，y∈∑*，xRMyδ(q0，x)=δ(q0，y) 根据RM的定义；δ(q0，y)=δ(q0，x) “=”的对称性；

yRMx 根据RM的定义。

2023/2/3595.3.1Myhill-Nerode定理传递性：设xRMy，yRMz。由于xRMy，δ(q0，x)=δ(q0，y)由于yRMz，

δ(q0，y)=δ(q0，z)由“=”的传递性知，

δ(q0，x)=δ(q0，z)再由RM的定义得：

xRMz即RM是等价关系。

2023/2/3605.3.1Myhill-Nerode定理⑵RM

是右不变的设xRMy。则δ(q0，x)=δ(q0，y)=q所以，对于z∈∑*，δ(q0，xz)=δ(δ(q0，x)，z))=δ(q，z)=δ(δ(q0，y)，z)=δ(q0，yz)这就是说，δ(q0，xz)=δ(q0，yz)，再由RM的定义，

xzRMyz所以，RM

是右不变的等价关系。

2023/2/3615.3.1Myhill-Nerode定理命题5-2

对于任意L∑*，L所确定的∑*上的关系RL为右不变的等价关系。证明：⑴RL是等价关系。

自反性显然。对称性：不难看出：xRLy(对z∈∑*，xz∈Lyz∈L)yRLx

2023/2/3625.3.1Myhill-Nerode定理传递性：设xRLy，yRLz。

xRLy(对w∈∑*，xw∈Lyw∈L) yRLz(对w∈∑*，yw∈Lzw∈L)所以，

(w∈∑*,xw∈Lyw∈L 且yw∈Lzw∈L)即：

(对w∈∑*，xw∈Lzw∈L)故：

xRLz即RL是等价关系。

2023/2/3635.3.1Myhill-Nerode定理⑵RL

是右不变的。

设xRLy。由RL的定义，对w，v∈∑*，xwv∈Lywv∈L，注意到v的任意性，知，xwRLyw。所以，RL是右不变的等价关系。

2023/2/3645.3.1Myhill-Nerode定理定义5-9指数(index)设R是∑*上的等价关系，则称|∑*/R|是R关于∑*的指数。简称为R的指数。简称∑*的关于R的一个等价类，也就是∑*/R的任意一个元素，为R的一个等价类

2023/2/3655.3.1Myhill-Nerode定理例5-9

图5-4所给DFAM所确定的RM的指数为6。RM将∑*分成6个等价类：

set(q0)={(00)n|n≥0}；

set(q1)={0(00)n|n≥0}；

set(q2)={(00)n1

|

n，m≥0}；

set(q3)={0(00)n1|n≥0}；

set(q4)={0n10k|n≥0，k≥1}；

set(q5)={x|x为至少含两个1的串}。2023/2/3665.3.1Myhill-Nerode定理RM是RL(M)的“加细”(refinement)x，y∈∑*，如果xRMy，必有xRL(M)y成立。即对于任意DFAM=(Q,∑,δ,q0,F)。

|∑*/RL(M)|≤|∑*/RM|≤|Q|按照RM中被分在同一等价类的串，在按照RL(M)分类时，一定会被分在同一个等价类。RM对∑*的划分比RL(M)对∑*的划分更“细”。称RM是RL(M)的“加细”(refinement)。

2023/2/3675.3.1Myhill-Nerode定理∑*/RM={set(q0)，set(q1)，set(q2)，set(q3)，set(q4)，set(q5)}⑴取00∈set(q0)，000∈set(q1)。对于任意的x∈∑*，当x含且只含一个1时，00x∈L(M)，000x∈L(M)；当x不含1或者含多个1时，00xL(M)，000xL(M)。这就是说，对于任意的x∈∑*，00x∈L(M)000x∈L(M)。即按照RL(M)，00与000被分在同一个等价类中。从而set(q0)和set(q1)被包含在RL(M)的同一个等价类中。

2023/2/3685.3.1Myhill-Nerode定理⑵取00∈set(q0)，001∈set(q2)。取特殊的字符串1∈∑*，001∈L(M)，但0011L(M)。所以，根据RL(M)，set(q0)和set(q2)不能被“合并”到一个等价类中。类似地，根据RL(M)，set(q3)、set(q4)、set(q5)也都不能被“合并”到set(q0)的句子所在的等价类中。

2023/2/3695.3.1Myhill-Nerode定理⑶取001∈set(q2)，01∈set(q3)。对于任意的x∈∑*，x要么不含1，要么含有1。当x不含1时，001x∈L(M)，01x∈L(M)；

当x含有1时，001xL(M)，01xL(M)。这就是说，对于任意的x∈∑*，001x∈L(M)01x∈L(M)。即按照RL(M)，001与01属于RL(M)的同一个等价类中。从而set(q2)和set(q3)被包含在RL(M)的同一个等价类中。

2023/2/3705.3.1Myhill-Nerode定理⑷取1∈set(q2)，

10∈set(q4)。对于任意的x∈∑*，x要么不含1，要么含有1。当x不含1时，1x∈L(M)，10x∈L(M)；当x含有1时，1xL(M)，10xL(M)。这就是说，对于任意的x∈∑*，1x∈L(M)10x∈L(M)。即按照RL(M)，1与10被分在RL(M)的同一个等价类中。从而在set(q2)和set(q4)被包含在RL(M)的同一个等价类中。

2023/2/3715.3.1Myhill-Nerode定理⑸取1∈set(q2)，

11∈set(q5)。注意1ε=1，11ε=11；而1∈L(M)，11L(M)。即1和11不满足关系RL(M)，所以，set(q2)和set(q5)不能被“合并”到RL(M)的同一个等价类中。在这里，ε∈∑*是一个特殊的字符串。2023/2/3725.3.1Myhill-Nerode定理∑*/RL(M)={set(q0)∪set(q1)，set(q2)∪set(q3)∪set(q4)，set(q5)}不含1：[0]=set(q0)∪set(q1)=0*；含一个1：[1]=set(q2)∪set(q3)∪set(q4)=0*10*；含多个1：[11]=set(q5)=0*10*1(0+1)*。

2023/2/3735.3.1Myhill-Nerode定理定理5-7(Myhill-Nerode定理)如下三个命题等价：

⑴

L∑*是

RL；⑵

L是∑*上的某一个具有有穷指数的右不变等价关系R的某些等价类的并；⑶

RL具有有穷指数。2023/2/3745.3.1Myhill-Nerode定理证明：

由(1)可以推出(2)设L∑*是

RL，所以，存在DFAM=(Q，∑，δ，q0，F)，使得L(M)=L。由命题5-1，RM是∑*上的右不变等价关系，而且|∑*/RM|≤|Q|，所以，RM具有有穷指数。而

L是∑*上的具有有穷指数的右不变等价关系RM的、对应于M的终止状态的等价类的并。

2023/2/3755.3.1Myhill-Nerode定理由(2)可以推出(3)。设xRy，由R的右不变性可知，对于任意z∈∑*，xzRyz而L是R的某些等价类的并，所以，xz∈Lyz∈L根据RL的定义，xRLy故R是RL的加细。由于R具有有穷指数，所以，RL具有有穷指数。

2023/2/3765.3.1Myhill-Nerode定理由(3)可以推出(1)。令M′=(∑*/RL,∑,δ′,[ε],{[x]|x∈L})[ε]表示ε所在的等价类对应的状态；[x]表示x所在的等价类对应的状态。对于([x],a)∈(∑*/RL)×∑,δ′([x],a)=[xa]δ′定义的相容性:如果[x]=[y]，对a∈∑,有[xa]=[ya]。

L(M′)=L2023/2/3775.3.1Myhill-Nerode定理例5-10

用定理5-7证明{0n1n|n≥0}不是

RL根据L的句子的特征来寻找RL的等价类。

L的句子的主要特点有两个：⑴

句子中所含的字符0的个数与所含的字符1的个数相同。⑵

所有的0都在所有的1的前面可以得到如下一些等价类。2023/2/3785.3.1Myhill-Nerode定理[10]={x|x=0n1m(m≥n+1)或者x中含子串10}[ε]——ε所在的等价类；[1]——0所在的等价类；[2]——00所在的等价类；[3]——000所在的等价类；…[n]——0n所在的等价类；…所以，RL的指数是无穷的。因此，L不是

RL。2023/2/3795.3.1Myhill-Nerode定理推论5-1

对于任意的

RLL，如DFAM=(Q，∑，δ，q0，F)满足L(M)=L，则|∑*/RL|≤|Q|。表明对任意一个

RLL，按照定理中所给的方法构造出来的DFAM′是一个接受L的最小DFA。这个DFA是唯一的么？

2023/2/3805.3.1Myhill-Nerode定理推论5-2

对于任意的

RLL，同构意义下，接受L的最小DFA是唯一的。作业7(1)(3)(8)2023/2/3825.3.2DFA的极小化定义5-10可以区分的(distinguishable)状态设DFAM=(Q，∑，δ，q0，F)，如果x∈∑*，

对Q中的两个状态q和p，使得δ(q，x)∈F和δ(p，x)∈F中，有且仅有一个成立，则称p和q是可以区分的。否则，称q和p等价。并记作q≡p

。2023/2/3835.3.2DFA的极小化算法5-1DFA的极小化算法算法思想：扫描所有的状态对，找出所有的可区分的状态对，不可取分的状态对一定是等价的。输入：给定的DFA。输出：可区分状态表。主要数据结构：状态对的关联链表；可区分状态表。

2023/2/3845.3.2DFA的极小化主要步骤⑴for

(q，p)∈F×(Q-F)do

标记可区分状态表中的表项(q，p)；⑵for(q,p)∈F×F∪(Q-F)×(Q-F)&q≠pdo⑶ if

a∈∑，可区分状态表中的表项(δ(q，a)，δ(p，a))已被标记

then begin⑷ 标记可区分状态表中的表项(q，p)；⑸ 递归地标记本次被标记的状态对的关联链表上的各个状态对在可区分状态表中的对应表项

end

2023/2/3855.3.2DFA的极小化⑹ elsefor

a∈∑，do⑺ ifδ(q，a)≠δ(p，a)&(q，