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

编译原理2014—2015学年第二学期单元测试试卷模板（闭卷考试）时间：45分钟满分：100分姓名班级出题人邢少强班级12-3题目一二三四五总分得分一、选择题（5*2分）（每题2分，共10分）1．正规式M1和M2等价是指（）A．()M1和M2的状态数相等B．()M1和M2的有向边条数相等C．()M1和M2所识别的语言集相等D．()M1和M2状态数和有向边条数相等2．（）型文法也称为正规文法。A.0B.1C.2D.33．文法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.设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，，{A}，{C})，其中：(A，0)={C}(A，1)={A，B}(B，1)={C}(C，1)={C}。请画出状态转换距阵和状态转换图。（15分）10、有穷状态自动机M接受字母表Σ={0,1}上所有满足下列条件的串：串中至少包含两个连续的0或两个连续的1.（20分）（1）、请给出与M等价的正规式。（2）、将M最小化（3）、构造与M等价的正规文法。11证明正规式(ab)*a与正规式a(ba)*等价（用构造他们的最小的DFA方法）。（20分）