第二章词法试卷.ppt

图2-16 习题2.7的最简DFA 图2-17 正规式(a|b)*b对应的NFA 用子集法将图2-17所示的NFA确定化为如图2-18所示的状态转换矩阵。 图2-18 图2-17确定化后的状态转换矩阵 比较图2-18与图2-15，重新命名后的转换矩阵是完全一样的，也即正规式(a|b)*b可以同样得到化简后的DFA如图2-16所示。因此，两个自动机完全一样，即两个正规文法等价。 (2) 对图2-16，令A对应状态1，B对应状态2，则相应的正规文法G[A]为 G[A]：A→aA|bB|b B→aA|bB|b G[A]可进一步化简为G[S]：S→aS|bS|b(非终结符B对应的产生式与A对应的产生式相同，故两非终结符等价，即可合并为一个产生式)。 2.8 下列程序段以B表示循环体，A表示初始化，I表示增量，T表示测试： I=1; while (I=n) { sun=sun+a[I]; I=I+1; } 请用正规表达式表示这个程序段可能的执行序列。 【解答】 用正规表达式表示程序段可能的执行序列为A(TBI)*。 2.9 将图2-19所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。 图2-19 习题2.9的NFA 其中，X为初态，Y为终态。 【解答】 用子集法将NFA确定化，如图2-20所示。 图2-20 习题2.9的状态转换矩阵 图2-20所对应的DFA如图2-21所示。 图2-21 习题2.9的DFA 图2-22 习题2.9的最简DFA 对图2-21的DFA进行最小化。首先将状态分为非终态集和终态集两部分：{0,1,2,5}和{3,4,6,7}。由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其化为分 {0,1,2,5}, {4}, {3,6,7} 对于非终态集，在输入字符a、b后按其下一状态落入的状态集不同而最终划分为 {0}, {1}, {2}, {5}, {4}, {3,6,7} 按顺序重新命名为0、1、2、3、4、5，得到最简DFA如图2-22所示。 2.10 有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放≥3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。 (1) 写出售货机售糖的正规表达式； (2) 构造识别上述正规式的最简DFA。 【解答】 (1) 设a=1，b=2，则售货机售糖的正规表达式为a (b|a(a|b))|b(a|b)。 (2) 画出与正规表达式a(b|a(a|b))|b(a|b)对应的NFA，如图2-23所示。 图2-23 习题2.10的NFA 用子集法将图2-21的NFA确定化，如图2-24所示。 图2-24 习题2.10的状态转换矩阵 由图2-24可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态，即最简状态{0}、{1}、{2，3}、{4}。按顺序重新命名为0、1、2、3，则得到最简DFA，如图2-25所示。 图2-25 习题2.10的最简DFA 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 第二章 词法分析 第二章 词法分析 第二章 词法分析 2.1 完成下列选择题： (1) 词法分析器的输出结果是 。 a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M2等价是指 。 a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等 (3) DFA M(见图2-1)接受的字集为 。 a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数