画出下列有限自动机的状态转换图.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为首