《编译原理》3,4两章练习题 1.下图是一个ε-NFA的状态转移图,应用简化的子集构造法将该e-NFA转化为与其相等 价的DFA Start b 2.下图表示一个DFA,构造出与该DFA等价的最小化的DFA(即拥有的状态数目最少 Start 3.求出与正规表达式ab+(b+c)*等价的一个8-NFA。(直接写出结果即可 4.设计一个DFA,其语言为所有长度至少为2且头两个字符不相同的0,1串构成的集合 (以状态转移图的形式给出 5.设计一个NFA,其语言为所有长度至少为2且末尾两个字符不相同的0,1串构成的集 合。(以状态转移图的形式给出 6.设计一个正规表达式,其语言为所有至少包含2个“0″”的0,1串构成的集合。7.设 计如下语言的一个上下文无关文法: L={ab/m≥0} 8.(R+S)*=R*s*+SR*是否可以作为关于正规表达式的一条定律?为什么?《编译原理》3,4 两章练习题 1. 下图是一个–NFA 的状态转移图，应用简化的子集构造法将该 –NFA 转化为与其相等 价的 DFA。 0 Start 1 2 6 3 5 4     a b a  2. 下图表示一个 DFA，构造出与该 DFA 等价的最小化的 DFA（即拥有的状态数目最少）。 1 5 Start 2 b 3 4 b a a a a b b a b 6 a b 3. 求出与正规表达式 a*b+(b+c)* 等价的一个–NFA。(直接写出结果即可) 4. 设计一个 DFA，其语言为所有长度至少为 2 且头两个字符不相同的 0，1 串构成的集合 （以状态转移图的形式给出）。 5. 设计一个 NFA，其语言为所有长度至少为 2 且末尾两个字符不相同的 0，1 串构成的集 合。（以状态转移图的形式给出）。 6. 设计一个正规表达式，其语言为所有至少包含 2 个“0”的 0，1 串构成的集合。7. 设 计如下语言的一个上下文无关文法： L = { anbn | n≥0 } 8. (R+S)* = R*S* + S*R* 是否可以作为关于正规表达式的一条定律？为什么？