大连理工大学编译原理复习介绍

D. DFA可以有多个接受状态 答案：A （2）NFA 的构造 [简答题 10分] [1] 设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，?，{A}，{C})，其中： ? (A，0)={C} ? (A，1)={A，B} ? (B，1)={C} ? (C，1)={C}。请画出状态转换距阵和状态转换图。 答案： 状态转换距阵为： ? A B C 0 C ? ? 1 A，B C C 状态转换图为： 1 1 AB 0 [2] 构造正规式相应的 NFA : 1(0|1)*101。 答案： 1 1 C1

[3] 为（（ε|a）b*）* 构造非确定的有限自动机，给出它们处理输入串ababbab的转换序列。 答案： 输入串ababbab的转换序列： 0 1456789 145678 789 1456789 10 或者 0 1456789 1456789 1236789 1456789 10 （3）NFA转化为 DFA [简答题 10分] [1] 设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。 答案：构造相应的正规式：(0|1)*1(0|1) NFA:

确定化： I {0,1,2} {1,2} {1,2,3} {1,2,4} {1,2,3,4} I0 {1,2} {1,2} {1,2,4} {1,2} {1,2,4} I1 {1,2,3} {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4} 、 [2] 构造正规式 1(0|1)*101 相应的DFA。 答案：先构造NFA：

确定化： 重新命名，令AB为B、AC为C、ABY为D得： 所以，可得DFA为： [3] 对于下图所示NFA，回答下列问题：