（1）用正规式描述该有限自动机所表示的语言。 （2）由NFA转为DFA。 （3）构造最简DFA。 答案： （1）(a|b)*a(a|b)* （2） （3） （4）DFA的化简 [简答题 10分]
[1] 已知 NFA= （ {x,y,z},{0,1},M,{x},{z} ），其中： M(x,0)={z}, M(y,0)={x,y}, M(z,0)={x,z}, M(x,1)={x}, M(y,1)= φ ,M(z,1)={y}, 构造相应的DFA并最小化。 答案：根据题意有NFA图: 下表由子集法将NFA转换为DFA： 面将该DFA最小化：
(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F} (2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。 (3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。 (5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下： [2] 给定下列自动机： 把此自动机转换为确定自动机DFA。 答案： 有状态矩阵如图：
从而可得DFA如图： [3] （1）将下图中的NFA M确定化为DFA M’。 （2）将DFA M’化简。 a0aab1 答案： 确定化: {0} {1} a {0,1} {0} b {1} ---
相关推荐：
loading