第三章习题解答

第三章习题解答1．Pascal和C语言的字母是什么？==pascal语言的字母表是：{0，1，…，9}∪{a，…，z}∪{A，…，Z}∪{+，-，*，/，\，↑，?，?，_，(，)，[，]，;，:，=，<，>，'，"，Enter，Space，Tab}C语言的字母表是：{_,0…9,a…z,A…Z,+,-,*,/,\,%,(,),[,],.,&,|,！,=,#,{,},’,”,?,:，<，>，Enter，Space，Tab}====3.Pascal程序段，试问词法阶段能发现哪些词法错误？    ifa=1.thenb:=1.0elsec:=1;a:=bc+d;==ifa=1.(1)thenb:(2)=1.0elsec:(3)=1;a:(4)=bc+d;(1)第一个等号右边的数字1.写法不:不符合实数的词法规范(2)字母b,c和第二个a后边的赋值符号不会被识别出来，因为：和＝之间有空格，会被识别为两个符号分别是冒号“：”和等号“＝”====4．写出识别下列正则表达式定义的单词的DFA：(1)((a|bc)*d)+(2)((0|1)*(2|3)+)|0011(3)(aNot(a))aaa======5．写出定义Pascal类定点10进制小数的正则表达式。其要求是前面和后面没有多余的0，例如，0.0，0，123.01和123005.0是合法的；而00.0，002456.1000和001.00是非法的。==D={0,1,…,9}Decimal=(0|(D–{0})D*).(D*(D–{0})|0)====7.写出对应正则表达式(0|1)*0(0|1)n的NFA示意图,其中n是大于等于0的整数。证明NFA的等价的DFA的状态个数将按指数级增大，即假设NFA的状态个数为M,则DEA的状态个数是M^n级的======6．构造一个DFA，它接受的符号串集合等于正则表达式(ab*c)|(abc*)所示的字符串集合。要求先构造NFA，其次转换成DFA，最后加以极小化。======8．写出与下面DFA等价的正则表达式。==正则表达式为：(ε|a+a|hb*h)正则表达式为：a((hc|c)da)*====9．当构造词法分析器时，根据单词的正则表达式定义首先构造NFA，之后将NFA转换成DFA，并用其DFA进行词法分析。从正则表达式到NFA的转换块，而NFA到DFA的转换比较慢，因此在某些场合下，用NFA并按NFA到DFA的转换思想进行词法分析可能是很有意思的。就是说，在NFA的一个状态下，遇到一个字符时，用NFA到DFA时的构造技术确定下一状态。试写出算法。==procedureNextState(instate:inState,a:inchar,outState:outState)   BEGIN      for(元素ssinState)      BEGIN         ss1:=close(MoveSet(ss,a,NFA.TT));         outState:=outState∪ss1;      END   END====10．设DFA1和DFA2是同一字母表上的不同确定自动机，写出等价性判定算法。==算法：(1)将DFA1和DFA2分别化简得最简自动机DA1和DA2，若DA1和DA2状态数不等，则不等价，停止；否则转(2)(2)将DA2的初状态改为与DA1的初状态相同，设为S1_0；令ss={S1_0},News={S1_0}(3)从News中任选一个状态Sn,对每一个字符a，比较DA1.TT(Sn,a)和DA2.TT(Sn,a)[1]若二者其中一个为空，不等价，停止[2]若二者均不为空，但DA2.TT(Sn,a)是DA1中状态且不等于DA1.TT(Sn,a),不等价，停止[3]若二者均不为空，DA2.TT(Sn,a)不是DA1中状态，则将DA2.TT(Sn,a)改为与DA1.TT(Sn,a)相同,若DA1.TT(Sn,a)不在集合ss中，则将其加入News;    (4)从News中删去Sn,若News为空，二者等价，停止；否则转(3)