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

精选优质文档-倾情为你奉上编译原理20142015学年第二学期单元测试试卷模板（闭卷考试） 时间：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. 33 文法 G 所描述的语言是_的集合。A. 文法 G 的字母表 V 中所有符号组成的符号串B文法 G 的字母表 V 的闭包 V* 中的所有符号串C由文法的开始符号推出的所有终极符串D. 由文法的开始符号推出的所有符号串4词法分析器用于识别( ) A. 字符串 B语句 C单词 D标识符5词法分析器的输出结果是( ) A 单词的种别编码 B单词在符号表中的位置C单词的种别编码和自身值 D单词自身值2、 简答题（2*10分）（每题10分，共20分）6令=a,b，则正规式a*b|b*a 表示的正规集是什么？ 7.简述 DFA 与 NFA 有何区别 ?3、 分析题（4题共70分）8、描述由正规式b*(abb*)*(a| e)定义的语言，并画出接受该语言的最简DFA。（15分）9. 设有非确定的有自限动机NFA M=(A，B，C，0，1，d，A，C)，其中：d (A，0)=C d (A，1)=A，B d (B，1)=C d (C，1)=C。请画出状态转换距阵和状态转换图。（15分）10、 有穷状态自动机M接受字母表=0,1上所有满足下列条件的串：串中至少包含两个连续的0或两个连续的1.（20分）（1） 、请给出与M等价的正规式。（2） 、将M最小化（3） 、构造与M等价的正规文法。11证明正规式(ab)*a 与正规式a(ba)*等价 （用构造他们的最小的DFA方法）。（20分） 专心-专注-专业