资源描述：
《画出下列有限自动机的状态转换图.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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)={e,00,11,0101,0110,1001,1010,0011,0000,1111,…,}由偶数个0或偶数个1组成的二进制串。②M＝({0，1，2}
2、，{a，b}，f，0，{2})，其状态转移矩阵为：符号状态ab0{1,2}{0}1{0,1}f2{0,2}{1}解答：有限自动机M的状态转换图：有限自动机M所识别或接受的语言是：L(M)={a,aaa,abaa,ba,baaa,babaa,…}习题来源：编译技术（王力红）习题解答：黎远松3-2设计字母表∑={a,b}上的确定有限自动机，使它能识别或接受下列语言：①以aa为首的所有符号串集合；解答：正则式e=aa(a
3、b)*NFA：DFA：ab01f12,3,4f2,3,43,43,43,43,43,4最小化：ab2333332，3等价
4、，合并。ab0112习题来源：编译技术（王力红）习题解答：黎远松①以aa结尾的所有符号串集合；e=(a
5、b)*aaIIaIbXX,AXX,AX,A,YXX,A,YX,A,YX重命名：{X}为0{X,A}为1{X,A,Y}为2ab010120220②含有相继两个a或相继两个b的所有符号串集合。e=(a
6、b)*(aa
7、bb)(a
8、b)*习题来源：编译技术（王力红）习题解答：黎远松3-3试把下述NFA变换为DFA。解答：最基本的方法是子集法：IIaIb{0}{1}-{1}-{1，2}{1，2}{1}{1，2}重命名：{0}为0，{1}为1，
9、{1，2}为2，包含原终态2的{1，2}为新终态，于是所求DFA为：习题来源：编译技术（王力红）习题解答：黎远松解：最基本的方法：子集法：IIaIb{0}{1}-{1}-{1，2}{1，2}{0}{1，2}重命名：IIaIb01-1-2202习题来源：编译技术（王力红）习题解答：黎远松3-4试把下列eFA变换为非eFA。参考答案：用子集法确定化：b0，1，21,21,21,2最小化：b01110，1等价。合并：习题来源：编译技术（王力红）习题解答：黎远松用子集法：ab01,0f1,01,02,32,32,31,0习题来源：编译技术（王
10、力红）习题解答：黎远松3-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}。进一步计算：ab
11、2134052，4等价。ab3325543，5等价。合并等价状态，最小化为：习题来源：编译技术（王力红）习题解答：黎远松3-6构造下列正则表达式对应的确定有限自动机。①a(b
12、a)*aba②a(abab*
13、a(bab)*a)*b3-7写出下列FA所对应的正则表达式。①在FAM的转换图上加进一个初态结X和一个终态结Y。消去(0,1,b)这条弧：e=(a(b+a)*)*②消去(2,1,a)这条弧：e=ab(ab
14、ba
15、a)*3-8构造正则文法GLsl·S‘mBImB?’mBnSlm所对应的有限白动机。3-9给出下面的确定有限自动机所对应的
16、正则文法。3-11用某种高级语言写出：①非确定有限自动机确定化的算法；②有限自动机简化的算法；③把正则表达式转换为有限自动机的算法。
