编译原理第四章典型习题答案(共4页).docx

第四章1. 设字母表S=0，1，给出S上的正规式r=(0|10)*，请完成以下任务：1) 构造NFA M，使得L（M）=L（r）；2) 将NFA M确定化、最小化，得到最简DFA M，使得L（M）=L（M）。解：1）M为：(0|10)* 0 0 1 2) 1令T0=-closure(1)=1,2,4, T0未被标记，加入到子集族C中 2 标记T0，Move(T0,0)=2,-closure(Move(T0,0)=2,4=T1,T1未被标记，加入到子集族C中Move(T0,1)=3,-closure(Move(T0,1)=3=T2,T2未被标记，加入到子集族C中3 标记T1，Move(T1,0)=2,-closure(Move(T1,0)=2,4=T1,