《编译原理》第三单元测试.docVIP

《编译原理》第三单元测试 《编译原理》第三单元测试 PAGE 《编译原理》第三单元测试 编译原理 2014—2015学年第二学期单元测试试卷模板 （闭卷考试） 时间：45分钟 满分：100分 姓名　　 　 班级　　　　　　 出题人 邢少强 班级12-3 题目 一 二 三 四 五 总分 得分 一、选择题（5*2分）（每题2分，共10分） 1．正规式 M 1 和 M 2 等价是指（ ）? 　A．( ) M1和M2的状态数相等 ? 　 　?????? B．( ) M1和M2的有向边条数相等 　C．( ) M1和M2所识别的语言集相等 　　D．( ) M1和M2状态数和有向边条数相等 2．（ ）型文法也称为正规文法。 A. 0 B. 1 C. 2 D. 3 3． 文法 G 所描述的语言是_____的集合。 A. 文法 G 的字母表 V 中所有符号组成的符号串 B．文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．由文法的开始符号推出的所有终极符串 D. 由文法的开始符号推出的所有符号串 4．词法分析器用于识别( ) A. 字符串 B．语句 C．单词 D．标识符 5．词法分析器的输出结果是( ) A． 单词的种别编码 B单词在符号表中的位置 C．单词的种别编码和自身值 D．单词自身值 简答题（2*10分）（每题10分，共20分） 6．令Σ={a,b}，则正规式a*b|b*a 表示的正规集是什么？ 7.简述 DFA 与 NFA 有何区别 分析题（4题共70分） 8、描述由正规式b*(abb*)*(a| ?)定义的语言，并画出接受该语言的最简DFA。（15分） 9. 设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，?，{A}，{C})，其中： ? (A，0)={C} ? (A，1)={A，B} ? (B，1)={C} ? (C，1)={C}。请画出状态转换距阵和状态转换图。（15分） 有穷状态自动机M接受字母表Σ={0,1}上所有满足下列条件的串：串中至少包含两个连续的0或两个连续的1.（20分） 、请给出与M等价的正规式。 、将M最小化 、构造与M等价的正规文法。 　 11证明正规式(ab)*a 与正规式a(ba)*等价 （用构造他们的最小的DFA方法）。（20分）