习题3
3-1 画出下列有限自动机的状态转换图,并说明它所识别或接受的语言是什么?
①M=({S,A,B,C},{0,1},f,S,{S}),其转换函数为:
f(S,0)=B f(B,0)= S
f(S,1)=A f(B,1)= C
f(A,0)=C f(C,0)= A
f(A,1)=S f(C,1)= B
参考答案:有限自动机的状态转换图
它所识别或接受的语言是:
L(M)={ε,00,11,0101,0110,1001,1010,0011,0000,1111,…,}
由偶数个0或偶数个1组成的二进制串。
②M=({0,1,2},{a,b}
解答:有限自动机M的状态转换图:
有限自动机M所识别或接受的语言是:
L(M)={a,aaa,abaa,ba,baaa,babaa,…}
3-2设计字母表∑={a,b}上的确定有限自动机,使它能识别或接受下列语言:①以aa为首的所有符号串集合;
解答:
正则式e=aa(a | b)*
NFA:
最小化:
2
习题来源:编译技术(王力红)习题解答:黎远松②以aa结尾的所有符号串集合;
e=(a|b)*aa
{X}为0
{X,A}为1
③含有相继两个a或相继两个b的所有符号串集合。
e=(a|b)*(aa|bb)(a|b)*
3-3 试把下述NFA变换为DFA。
解答:
最基本的方法是子集法:
重命名:
{0}为0,{1}为1,{1,2}为2,包含原终态2的{1,2}为新终态,于是所求DFA为:
习题来源:编译技术(王力红)习题解答:黎远松
解:最基本的方法:子集法:
重命名:
3-4 试把下列εFA变换为非εFA。
参考答案:
习题来源:编译技术(王力红)习题解答:黎远松
用子集法:
3-5 试把下列FA确定化(若需要的话)和最小化。
参考答案:
2,4状态是死状态,应删除。
只有一个状态的FA肯定是确定化的和最小化的。
习题来源:编译技术(王力红)习题解答:黎远松
此FA是DFA,不需要确定化。
最小化:
首先按终态与非终态划分:{0,1},{2,3,4,5};然后计算:
对于输入a,b,{0,1}1等价。
对于输入a,{2,4}后继属于同一集合{0,1},{3,5}后继属于同一集合{3,5},故可继续划分为:{2,4},{3,5}。进一步计算:
3,5等价。
合并等价状态,最小化为:
3-6 构造下列正则表达式对应的确定有限自动机。
①a(b | a)*aba
②a(abab* | a(bab)*a)*b
3-7 写出下列FA所对应的正则表达式。
①在FA M的转换图上加进一个初态结X和一个终态结Y。消去(0,1,b)这条弧:
e=(a(b+a)*)*
②消去(2,1,a)这条弧:e=ab(ab|ba|a)*
3-8 构造正则文法GLsl
·S‘mBI m
B?’mB nSlm
所对应的有限白动机。
3-9 给出下面的确定有限自动机所对应的正则文法。
3-11 用某种高级语言写出:
①非确定有限自动机确定化的算法;
②有限自动机简化的算法;
③把正则表达式转换为有限自动机的算法。