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

1、习题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)=,OO,11,O1O1,O11O,1OO1,1O1O,OO11,OOOO,1111,.,由偶数个0或偶数个1组成的二进制串。M=(0,1,2,a,b,f,0,2),其状态转移矩阵为：、符号状态、ab01,2010,1020,21解答：有限自动机M的状态转换图:有限自动机

2、M所识别或接受的语言是:L(M)=a,aaa,abaa,ba,baaa,babaa,.3-2设计字母表=a,b上的确定有限自动机，使它能识别或接受下列语言:以aa为首的所有符号串集合；解答：正则式e=aa(a|b)*NFA：aDFA：ab0112,3,42,3,43,43,43,43,43,4a最小化：ab2333332，3等价，合并。ab0112a以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|

3、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，2IIaIb01-1-2202a习题来源：编译技术（王力红）习题解答：黎远松

4、习题来源：编译技术（王力红）习题解答：黎远松3-4试把下列卩人变换为#FA。参考答案：用子集法确定化：0,1,2回1,2最小化：00S0,1等价。合并:h习题来源：编译技术（王力红）习题解答：黎远松习题来源：编译技术（王力红）习题解答：黎远松用子集法：习题来源：编译技术（王力红）习题解答：黎远松习题来源：编译技术（王力红）习题解答：黎远松3-5试把下列FA确定化（若需要的话）和最小化。只有一个状态的FA肯定是确定化的和最小化的。习题来源：编译技术（王力红）习题解答：黎远松习题来源：编译技术（王力红）习题解答：黎远松此FA是DFA，不需要确定化。最小化：首先按终态与非终态划分：0，1，2，3，4，5；然后计算：对于输入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)*abaa(abab*|a(bab)*a)*b消去(2,l,a)这条弧：e=ab(ablbala)*3-8构造正则文法GLslSmBImB?mBnSlm所对应的有限白动机。3-9给出