第二章 词法分析
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的二进制数组成的集合
【解答】
(1) c (2) c (3) d
图2-1 习题2.1的DFA M
2.2 什么是扫描器?扫描器的功能是什么?
【解答】 扫描器就是词法分析器,它接受输入的源程序,对源程序进行词法分析并识别出一个个单词符号,其输出结果是单词符号,供语法分析器使用。通常是把词法分析器作为一个子程序,每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时,词法分析器就从输入串中识别出一个单词符号交给语法分析器。
2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机,其中f定义如下:
f(x,a)={x,y} f{x,b}={y}
f(y,a)=Φ f{y,b}={x,y}
试构造相应的确定有限自动机M′。
【解答】 对照自动机的定义M=(S,Σ,f,So,Z),由f的定义可知f(x,a)、f(y,b)均为多值函数,因此M是一非确定有限自动机。
先画出NFA M相应的状态图,如图2-2所示。
图2-2 习题2.3的NFA M
用子集法构造状态转换矩阵,如表2-1所示。
表2-1 状态转换矩阵
将转换矩阵中的所有子集重新命名,形成表2-2所示的状态转换矩阵,即得到
M′=({0,1,2},{a,b},f,0,{1,2}),其状态转换图如图2-3所示。
表2-2 状态转换矩阵
将图2-3所示的DFA M′最小化。首先,将M′的状态分成终态组{1,2}与非终态组{0}。其次,考察{1,2},由于{1,2}a={1,2}b={2} {1,2},所以不再将其划分了,也即整个划分只有两组:{0}和{1,2}。令状态1代表{1,2},即把原来到达2的弧都导向1,并删除状态2。最后,得到如图2-4所示的化简了的DFA M′。
图2-3 习题2.3的DFA M′
图2-4 图2-3化简后的DFA M′
2.4 正规式(ab)*a与正规式a(ba)*是否等价?请说明理由。
【解答】 正规式(ab)*a对应的NFA如图2-5所示,正规式a(ba)*对应的NFA如图2-6所示。
图2-5 正规式(ab)*a对应的NFA
图2-6 正规式a(ba)*对应的DFA
这两个正规式最终都可得到最简DFA,如图2-7所示。因此,这两个正规式等价。
图2-7 最简NFA
2.5 设有L(G)={a2n+1b2ma2p+1| n≥0,p≥0,m≥1}。
(1) 给出描述该语言的正规表达式;
(2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。
【解答】 该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*,正规表达式对应的NFA如图2-8所示。
图2-8 习题2-5的NFA
用子集法将图2-8确定化,如图2-9所示。
由图2-9重新命名后的状态转换矩阵可化简为(也可由最小化方法得到)
{0,2} {1} {3,5} {4,6} {7}
按顺序重新命名为0、1、2、3、4后得到最简的DFA,如图2-10所示。
图2-9 习题2.5的状态转换矩阵
图2-10 习题2.5的最简DFA
2.6 有语言L={w|w∈(0,1)+,并且w中至少有两个1,又在任何两个1之间有偶数个0},试构造接受该语言的确定有限状态自动机(DFA)。
【解答】 对于语言L,w中至少有两个1,且任意两个1之间必须有偶数个0;也即在第一个1之前和最后一个1之后,对0的个数没有要求。据此我们求出L的正规式为0*1(00(00)*1)*00(00)*10*,画出与正规式对应的NFA,如图2-11所示。
图2-11 习题2.6的NFA
用子集法将图2-11的NFA确定化,如图2-12所示。
图2-12 习题2.6的状态转换矩阵
由图2-12可看出非终态2和4的下一状态相同,终态6和8的下一状态相同,即得到最简状态为
{0}、{1}、{2,4}、{3}、{5}、{6,8}、{7}
按顺序重新命名为0、1、2、3、4、5、6,则得到最简DFA,如图2-13所示。
图2-13 习题2.6的最简DFA
2.7 已知正规式((a|b)*|aa)*b和正规式(a|b)*b。
(1) 试用有限自动机的等价性证明这两个正规式是等价的;
(2) 给出相应的正规文法。
【解答】 (1) 正规式((a|b)*|aa)*b对应的NFA如图2-14所示。
图2-14 正规式((a|b)*|aa)*b对应的NFA
用子集法将图2-14所示的NFA确定化为DFA,如图2-15所示。
图2-15 图2-14确定化后的状态转换矩阵
由于对非终态的状态1、2来说,它们输入a、b的下一状态是一样的,故状态1和状态2可以合并,将合并后的终态3命名为2,则得到表2-3(注意,终态和非终态即使输入a、b的下一状态相同也不能合并)。
由此得到最简DFA,如图2-16所示。
正规式(a|b)*b对应的NFA如图2-17所示。
表2-3 合并后的状态转换矩阵
图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-2习题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
本文来源:https://www.2haoxitong.net/k/doc/41295244336c1eb91a375d65.html
文档为doc格式