画出下列有限自动机的状态转换图.doc

习题来源：编译技术（王力红） 习题解答：黎远松习题33-1 画出下列有限自动机的状态转换图，并说明它所识别或接受的语言是什么？ M(S，A，B，C，0，1，f，S，S)，其转换函数为：f(S，0)=Bf(B，0)= Sf(S，1)=Af(B，1)= Cf(A，0)=Cf(C，0)= Af(A，1)=Sf(C，1)= B参考答案：有限自动机的状态转换图它所识别或接受的语言是：L(M)=e,00,11,0101,0110,1001,1010,0011,0000,1111,由偶数个0或偶数个1组成的二进制串。 M(0，1，2，a，b，f，0，2)，其状态转移矩阵为：符号状态ab01,2010,1f20,21解答：有限自动机M的状态转换图：有限自动机M所识别或接受的语言是：L(M)=a,aaa,abaa,ba,baaa,babaa,3-2设计字母表=a,b上的确定有限自动机，使它能识别或接受下列语言： 以aa为首的所有符号串集合；解答：正则式e=aa(a | b)*NFA：DFA：ab01f12,3,4f2,3,43,43,43,43,43,4最小化：ab2333332，3等价，合并。ab0112 以aa结尾的所有符号串集合；e=(a|b)*aaIIaIbXX,AXX,AX,A,YXX,A,YX,A,YX重命名：X为0X,A为1X,A,Y为2ab010120220 含有相继两个a或相继两个b的所有符号串集合。e=(a|b)*(aa|bb)(a|b)*3-3 试把下述NFA变换为DFA。解答：最基本的方法是子集法：IIaIb01-1-1，21，211，2重命名：0为0，1为1，1，2为2，包含原终态2的1，2为新终态，于是所求DFA为：解：最基本的方法：子集法：IIaIb01-1-1，21，201，2重命名：IIaIb01-1-22023-4 试把下列eFA变换为非eFA。参考答案：用子集法确定化：b0，1，21,21,21,2最小化：b01110，1等价。合并：用子集法：ab01,0f1,01,02,32,32,31,03-5 试把下列FA确定化(若需要的话)和最小化。参考答案：2,4状态是死状态，应删除。只有一个状态的FA肯定是确定化的和最小化的。此FA是DFA，不需要确定化。最小化：首先按终态与非终态划分：0，1，2，3，4，5；然后计算：ab012114对于输入a，b，0，1后继都属于同一集合，故0，1等价。ab21334055对于输入a， 2，4后继属于同一集合0，1，3，5后继属于同一集合3，5，故可继续划分为：2，4，3，5。进一步计算：ab2134052，4等价。ab3325543，5等价。合并等价状态，最小化为：3-6 构造下列正则表达式对应的确定有限自动机。 a(b | a)*aba a(abab* | a(bab)*a)*b3-7 写出下列FA所对应的正则表达式。 在FA M的转换图上加进一个初态结X和一个终态结Y。消去(0,1,b)这条弧：e=(a(b+a)*)* 消去(2,1,a)这条弧：e=ab(ab|ba|a)*3-8 构造正则文法GLsl SmBI m B?mB nSlm所对应的有限白动机。3-9 给出下面的确定有限自动机所