第二、三章习题讲解 2008-10-28

2.1 考虑下面的上下文无关文法： S → SS+ | SS* |a 试说明如何使用该文法生成串aa+a*。 试为aa+a*构造一个分析树。 该文法产生的语言是什么？ ANSWER: S SS* SS+S* aa+a* 图 以a为变量，+和*为二元操 作符的后缀表达式

2.2 下面的文法产生什么语言？ S→0S1|01 {0n1n（n=1,2,…）} S→+SS|-SS|a 括号的匹配 S→aSbS|bSaS| ε 由相同数目的a、b组成的字符串，或者空串。

S→a|S+S|SS|S*|(S) 以a为数据元素，具有合并、连接、闭包和括号操作符的表达式。a是表达式，若S是表达式则S+S（表达式的合并）、SS（表达式的串联）、S*（表达式的闭包运算）都是表达式。

注意事项 ε不是终结符，应该省略。但是如果包含空串，则需特别强调。 产生式可以交替使用 描述生成何种语言时，应当描述完整的字母表

2.3 练习2.2中哪些文法具有二义性？ c、d、e具有二义性。 可通过画某个串的分析树来说明

可以从句子abab有两个不同的最左推导来说明. S aSbS  abS  abaSbS  ababS  abab S  aSbS | bSaS | a) 试说明此文法是二义性的. 可以从句子abab有两个不同的最左推导来说明. S aSbS  abS  abaSbS  ababS  abab lm lm lm lm lm S aSbS  abSaSbS  abaSbS  ababS  abab lm lm lm lm lm 句子abab有两个不同的最左推导, 该句子是二义性的 . 所以此文法是二义性的.

(b) 对于句子abab构造两个相应的最右推导. S aSbS  aSb  abSaSb  abSab  abab rm rm rm rm rm S aSbS  aSbaSbS  aSbaSb  aSbab  abab rm rm rm rm rm (c)对于句子abab构造两个相应的分析树. 判断一个文法是否具有二义性，可以通过判断是否存在一个具有多棵分析树的记号串。

3. 3 识别下面的各段程序中构成记号的词素，并给出每个记号的合理属性值： 程序： int max（i，j）int i，j； / 3.3 识别下面的各段程序中构成记号的词素，并给出每个记号的合理属性值： 程序： int max（i，j）int i，j； /*返回整数i和j的最大者*/ { return i>j? i:j； }；

词素 记号 属性 int max id 指向符号表max条目的指针 ( 标点符号 左括号 i 指向符号表i条目的指针 , 逗号 j 指向符号表j条目的指针 ) 右括号 ; 分号 return > 操作符 大于号 ? 问号 : 冒号 { 右大括号 } 左大括号

注意事项 记号token（终结符），模式pattern，词素lexeme（源程序的字符序列） 每个词素都要一一记录 注释是在词法分析时忽略的，而词法分析器对程序采取非常局部的观点。 不是每个token都要有属性

3.6 试描述下列正规表达式所表示的语言: (a) 0 ( 0 | 1)* 0 由0和1组成且以0开始和结束的符号串全体. (b) ( (  | 0 ) 1* ) * 由0和1组成的符号串全体. (c) ( 0 | 1 )* 0 ( 0 | 1) ( 0 | 1) 由0和1组成且以000,001,010或011结束的符号串全体. 长度大于等于3且倒数第3个字符为0的01符号串全体.

(d) 0*10*10*10* 有且只有3个1的0、1字符串全体. (e) ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* 带有偶数个0和偶数个1的由0和1组成的符号串全体. 带有偶数个a和偶数个b的符号串全体. ( (aa|bb) | (ab|ba) (aa|bb)* (ab|ba) )*

注意事项 在描述语言的时候应该准确，精简。 语言－－给定字母表上任意一个字符串集合。 句子（字）－－属于语言的字符串，字母表中符号的有穷序列。 空字符串ε和空集φ

3.7 试写出下列语言的正规定义： a）包含5个元音的所有字母串，其中元音按顺序出现。 X={辅音字母全体} (X|(A|a))*(A|a) (X|(E|e))*(E|e) (X|(I|i))*(I|i) (X|(O|o)*(O|o) (X|(U|u)*(U|u)X* 保证元音字母至少出现一次

b) 按词典递增序排列的所有字母串。 ( a | A)* ( b | B)* ( c | C)*......( z | Z)*

 i  ri0ri1...ri9 d)没有重复出现的数字的数字符号串全体. 令 ri = i | , i=0,1,2,...,9 R0|R1|R2|...|R9记为  Ri i(0,1,2...,9) P(0,1,2...,9)表示0,1,2...,9的全排列  ri0ri1...ri9 i0i1... i9P(0,1,2...,9) e) 最多有一个重复出现的数字的数字符号串全体  i  ri0ri1...ri9 i(0,1,2...,9) i0i1... i9P(0,1,2...,9)

f) 带有偶数个0和奇数个1的由0和1组成的符号串全体. E为带有偶数个0和1的由0和1组成的符号串全体. 即 ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* E 1 E | E 0 E 1 E 0 E h) 不包含子串011的由0和1组成的符号串全体. 1*( 0 | (01) )* i) 不包含子序列011的由0和1组成的符号串全体 1*0* (10* |)

h) 不包含子串011的由0和1组成的符号串全体. 1*( 0 | (01) )* i) 不包含子序列011的由0和1组成的符号串全体 1*0* (10* |)

(00 | 11) ( (01 | 10) (00 | 11)  (01 | 10) (00 | 11)  )  所有由偶数个0和偶数个1构成的串。另外，和该正规式等价的正规式有( 00 | 11 | ( (01 | 10) (00 | 11)  (01 | 10) ) ) 。 更简单的描述 ( 00 | 11 | ( (01 | 10) (00 | 11)  (01 | 10) ) )  它是基于这样的考虑，满足要求的最简单的串有三种形式（空串除外）： 1．00 2．11 3．(01 | 10) (00 | 11)  (01 | 10) 它们任意多次的重复构成的串仍然满足要求。

写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规定义。 even_0_even_1 (00 | 11) ( (01 | 10) (00 | 11)  (01 | 10) (00 | 11)  )  even_0_odd_1  1 even_0_even_1 |0 (00 | 11) (01 | 10) even_0_even_1 对于偶数个0和奇数个1构成的串，其第一个字符可能是0或1。 如果是1，那么剩下的部分一定是偶数个0和偶数个1。 如果是0，那么经过若干个00或11，一定会出现一个01或10，才能保证0的个数是偶数，1的个数是奇数。若串还没有结束，剩余部分一定是偶数个0和偶数个1。

注意事项 正规定义：为了让正规表达式的表示简洁，可以对正规式命名。 应该写出正规定义或者正则表达式，状态图必须化简 d1  r1 . . . dn  rn 各个di的名字都不同 每个ri都是∪{d1, d2, …, di-1 }上的正规式 应该写出正规定义或者正则表达式，状态图必须化简

3.16 用算法3.3 构造非确定有穷自动机，给出处理输入串ababbab的状态转换序列： 23

ababbab的状态转换序列 24

c) ((|a)b*)* 25

ababbab的状态转换序列 26

3.17 用算法3.2把练习3.16中的NFA转换成DFA。给出它们处理串ababbab的状态转换序列。 -closure({0}) = {0,1,2,4,7} = A -closure(move(A,a)) = -closure({3}) = {1,2,3,4,6,7} = B -closure(move(A,b)) = -closure({5}) ={1,2,4,5,6,7} = C -closure(move(B,a)) = -closure({3}) = {1,2,3,4,6,7} -closure(move(B,b)) = -closure({5}) = {1,2,4,5,6,7} 27

-closure(move(C,a)) = -closure({3}) = {1,2,3,4,6,7} -closure(move(C,b)) = -closure({5}) = {1,2,4,5,6,7} 则DFA为： 28

3.17 用算法3.2把练习3.16中的NFA转换成DFA。给出它们处理串ababbab的状态转换序列。 c) (( |a)b*)* -closure({0}) = {0,1,2,3,4,6,7,8,10,11}=A -closure(move(A,a)) = -closure({5}) = {1,2,3,4,5,6,7,8,10,11}=B -closure(move(A,b)) = -closure({9}) ={1,2,3,4,6,7,8,9,10,11}=C 29

-closure(move(B,a)) = -closure({5}) = {1,2,3,4,5,6,7,8,10,11}=B -closure(move(B,b)) = -closure({9}) = {1,2,3,4,5,6,7,8,10,11}=C -closure(move(C,a)) = -closure({5}) = {1,2,3,4,5,6,7,8,10,11}=B -closure(move(C,b)) = -closure({9})= {1,2,3,4,5,6,7,8,10,11}=C 则DFA为： 30

画状态图注意事项 应明确地指出开始状态 应明确地指出终止状态，不一定只有一个 NFA转化为DFA时，NFA的状态集合包含有接受状态，那么对应的DFA状态也是接受状态 31

3.22 如果两个正规表达式的最少状态DFA除状态名以外完全相同，则这两个正规表达式等价。 (a*|b*)* A: -closure(0) = {0,1,2,3,5,6,7,9,10,11,} B: -closure(move(A,a)) = -closure(4) = {1,2,3,4,5,6,7,9,10,11} C: -closure(move(A,b)) = {1,2,3, 6,7,8,9,10,11} 32

状态 a b A B C A 33

注意事项 该题为证明题，做题思路为构造各个正规表达式的最小状态DFA。应该有中间步骤。 a)和c)可以见3.17中的解答。 34

3.23 对于下列正规表达式构造最小状态的DFA. 解题步骤： 1，从正则表达式到NFA 2，从NFA到DFA（子集构造法） 3，最小化DFA（算法3.6） 35

3.23 对于下列正规表达式构造最小状态的DFA. a) (a|b)*a(a|b) 36

(b) (a|b)*a(a|b)(a|b) 解法一 1 start 2 4 3 b NFA A start B a b H G C D E F 最小化DFA 37

b) (a | b) a (a | b) (a | b) 解法二 2 1 3 4 5 6 7 a b a,b start 图1.12 构造过程的第一步 2 1 3 4 5 6 7 a b start 图1.11 接收(a | b) a (a | b) (a | b)的DFA 38

c) (a | b) a (a | b) (a | b) (a | b) 一共有16个状态，满足定理3.23 d） 正规表达式(a | b) a (a | b) (a | b)… (a | b)共有n-1个(a | b)，对应的任何一个DFA至少有2^n个状态。 证明方法如前图方法所示。 39

第一步： ε a a ε 2 3 ε 9 ε ε start ε ε a 1 6 7 8 b b ε ε ε ε 4 5 ε a a ε ε 10 ε ε start ε ε a 1 6 7 8 13 b b ε ε ε ε 4 5 11 12 ε a a ε 14 15 19 20 ε ε ε 13 18 23 ε b b ε ε ε 16 17 21 22 图：带ε转移的NFA 40

第二步 A= -closure({0}) B= -closure({3,8}) C= -closure({5}) D= -closure({3,8,10}) E= -closure({5,12}) F= -closure({3,8,10,15}) G= -closure({5,12,17}) H= -closure({3,8,15}) I= -closure({5,17}) J= -closure({3,8,10,15,20}) K= -closure({5,12,17,22}) L= -closure({3,8,15,20}) M= -closure({5,17,22}) N= -closure({3,8,10,20}) O= -closure({5,12,22}) P= -closure({3,8,20}) Q= -closure({5,22}) 41

状态 a b A B C D E F G H I J K L M N O P Q 状态转移表： 42

第三步： 应用算法3.6消除状态C之后得到的最少状态DFA：

给出奇数个0奇数个1的正规表达式 1 start 1 1 1 2 3 1 接受奇数个0和奇数个1的的DFA 偶0偶1 偶0奇1 奇0偶1 1 1 1 2 3 1 奇0偶1 奇0奇1 接受奇数个0和奇数个1的的DFA 44

给出偶数个0和偶数个1的字符串的正规表达式 3 1 2 start 偶0偶1 奇0奇1 奇0偶1 偶0奇1 45

消除状态1： 3 2 11 10 1 01 start 00 46

消除状态2： 消除状态2： 3 11|00 10|01 01|10 start 00|11 47

即： (11|00)*(01|10)((11|00)*(01|10)(11|00)*(01|10))*(11|00)* 奇0奇1 11|00 消除状态3： (11|00)*(01|10)((11|00)*(01|10)(11|00)*(01|10))*(11|00)* 奇0奇1 3 3 11|00 (10|01)(00|11)*(01|10) start q f ((00|11)|((10|01)(00|11)*(01|10))* 即： start 48