清华大学：《编译原理》课程教学资源_第三章 练习题

《编译原理》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* 是否可以作为关于正规表达式的一条定律？为什么？

9.设计如下语言的一个上下文无关文法 L={ab/nkm0,且mm} 10.G[M:M→0A|1B A→1C|0M|0 B→0C|1M C+1A OB 定义的语言是什么? 11给出定义语言L=W|W是不含两个相邻的1的0,1串三型文法 12.按指定类型给出下列语言的文法 a)不以零开头的奇数集的三型文法 b)类 PASCAL风格的变量声明语句序列的上下文无关文法。一个声明语句可以声明一 序列变量(变量间逗号隔开),而后是一个冒号,再后是类型,类型可以是整型,实型,字 符型等等。如: a, b, c: integer; d real. 13.文法G:VN=},Ⅵ=仪&@a开始符号为E,P为 E->&E E@E a a)说明此文法是二义的 b)利用算符的优先性和结合性,将其改写为等价的无二义文法:其中@是右结合的 且优先性比&低 c)使用改写后的文法画出&a@a的语法树

9. 设计如下语言的一个上下文无关文法： L = { anbkcm | n, k, m≥0，且 n≥m } 10. G[M]: M→0A | 1B A→1C | 0M | 0 B→0C | 1M | 1 C→1A | 0B 定义的语言是什么？ 11 给出定义语言 L＝{W | W 是不含两个相邻的 1 的 0，1 串 }的三型文法。 12．按指定类型给出下列语言的文法. a)不以零开头的奇数集的三型文法 b) 类PASCAL风格的变量声明语句序列的上下文无关文法。一个声明语句可以声明一 序列变量（变量间逗号隔开），而后是一个冒号，再后是类型，类型可以是整型，实型，字 符型等等。如: a, b, c : integer; d : real; 13. 文法G：VN = {E} ，VT = {& @ a} 开始符号为 E，P为 E –> &E | E@E | a a) 说明此文法是二义的 b) 利用算符的优先性和结合性，将其改写为等价的无二义文法 ：其中 @ 是右结合的 且优先性比& 低. c)使用改写后的文法画出&a@a的语法树