《习题23》由会员分享，可在线阅读，更多相关《习题23（4页珍藏版）》请在金锄头文库上搜索。
1、习题二十三习题二十三1.写出表示下列语言的正规表达式，并证明你的表达式是正确的： (a) 字母表a, b, c上包含至少一个 a 和至少一个 b 的集合。 解：分析：只要保证在该集合中的任意符号串中至少含有一个 a 和至少一个 b 即可。 考虑到 a 和 b 都有可能在前面，因此每个符号串的形态为 w1aw2bw3或 w1bw2aw3，其中每 个 wi，i = 1, 2, 3，可以是任意的a, b, c上的符号串。故该集合的正规表达式为： (a + b + c)*a(a + b + c)*b(a + b + c)* + (a + b + c)*b(a + b + c)*a(a + b + c)
2、*。 (b) 倒数第 10 个符号是 1 的 0 和 1 的串的集合。 解：分析：倒数第 10 个是 1，前面有可能是 1 或者 0，最后 9 个也可能是 1 或者 0。因 此，该表达式为：(0 + 1)*1(0 + 1)9 。 (c) 至多只有一对连续 1 的 0 和 1 的串的集合。 解：分析：至多只有一对连续 1 的 0 和 1 的串的集合可分为两种情况。(1)不含连续 1 的符号串：(1 + )(0 + 01)*。(2)只含一对连续 1 的符号串：(0 + 10)*11(0 + 01)*。综合(1)和 (2)为：(1 + )(0 + 01)* | (0 + 10)*11(0 + 01)
3、*。2.写出表示下列语言的正规表达式： (a) 最多含有一对相邻的 0 和一对相邻的 1 的 0 和 1 的符号串的全体集合。 解：分析：因为符号串中最多含有一对相邻的 0 和一对相邻的 1，即表示其他的符号串 都由 01 或 10 组成。因此，该表达式为：(01)*(10)*(01)* + (10)*(01)*(10)*)。 (b) 每一对相邻的 0 都出现在每一对相邻的 1 的前面的 0 和 1 的符号串的全体集合。 解：分析：因为每对相邻的 0 都出现在每一对相邻的 1 前，则在出现 11，即连续的 1，之后不能出现连续的 0。也就是在连续的 1 后面出现的 0 必须被 1 隔开，除了最
4、后单独 一个 0 之外。因此，该表达式为：(0 + 10)*1*(01 + 1) *(0 + )。 (c) 所有含有相同数目的 0 和 1 并且任何前缀中 0 最多比 1 多一个且 1 最多比 0 多一个 的 0 和 1 的符号串的集合。 解：分析：因为符号串中任何前缀中 0 最多比 1 多一个且 1 最多比 0 多一个，则说明 串中不存在 00 和 11；又因为 0 和 1 的数目必须是相同的，所有出现一个 0 就必须出现一个 1，那么就是有 10 和 01 组成的符号串。因此，该表达式为：(01 + 10)*。 (d) 0 的个数被 5 整除的 0 和 1 的串的集合。 解：分析：该集合中
5、的符号串均由含 5 个 0 的子串构成，即(1*01*01*01*01*01*)*。 3.写出表示下列语言的正规表达式： (a) 不包含 101 作为子串的所有 0 和 1 的串的集合。 解：分析：字符串中不包含 101 作为子串，则要求符号串中的两个 1 之间不能有单个 0，即两个 1 之间可以没有 0 或有两个及两个以上的 0。即：0*(1 + 1000*+0*001)*4.给出下列正规表达式语言的自然语言描述： (a) (1+)(00*1)*0*。 解：任意 2 个 1 之间都被 0 隔开了的 0 和 1 的字符串的集合。(b) (0*1*)*000(0+1)*。 解：其中必定含有连续的
6、 3 个 0 的 0 和 1 的字符串的集合。(c) (0+10)*1*。解：连续的 1 只能出现在末尾的 0 和 1 的字符串的集合。5.验证下列关于正规表达式的恒等式。 (a)r + s = s + r。证明：令正规式 r 和 s 分别表示字符串集合 R 和 S。正规式 r + s 和 s + r 分别表示字符 串集合 RS 和字符串集合 SR。 由集合的并运算满足交换律可知，RS = SR，所以有 r + s = s + r。 由此可知正规式对运算+的交换律成立。 (b) (r + s) + t = r + (s + t)。 证明：令正规式 r、s 和 t 分别表示字符串集合 R、S 和
7、 T。正规式(r + s) + t 和 r + (s + t) 分别表示字符串集合(RS)T 和字符串集合 R(ST)。 由集合的并运算满足结合律可知，(RS)T = R(ST)，所以有(r + s) + t = r + (s + t)。 即正规式对运算+的结合律成立。 (c) (rs)t = r(st)。 证明：令正规式 r、s 和 t 分别表示字符串集合 R、S 和 T，则(rs)t 和 r(st)分别表示字符 串集合(RS)T 和 R(ST)。 对任意字符串 x(RS)T，则 x 必定由 3 个子串 x1、x2和 x3构成，即 x = x1x2x3，其中， x1R，x2S，x3T。于是
8、x = x1(x2x3)R(ST)。同理可证对任意字符串 yR(ST)，则必定有 y(RS)T。即 (RS)T = R(ST)。从而(rs)t = r(st)。 (d) r(s + t) = rs + rt。 证明：令正规式 r、s 和 t 分别表示字符串集合 R、S 和 T，则 r(s + t)和 rs + rt 分别表示 字符串集合 R(ST)和 RSRT。 对任意字符串 xR(ST)，则 x 必定由 2 个子串 x1和 x2构成，即 x = x1x2，其中， x1R，x2ST。若 x2S，则 x1x2RSRSRT；若 x2T，则 x1x2RTRSRT。总之xRSRT。 又对任意字符串 y
9、RSRT，则必定有 yRS 或 yRT。即 y 必定由 2 个子串 y1和 y2 构成，即 y = y1y2，其中，y1R，y2S 或 y2T。即 y2 ST。从而 y R(ST)。 故 R(ST) = RSRT。于是 r(s + t) = rs + rt。即正规式的联接运算对加运算的左分配率 成立。 (e) (r + s)t = rt + st。 证明：令正规式 r、s 和 t 分别表示字符串集合 R、S 和 T，则(r + s)t 和 rs + st 分别表示 字符串集合(RS)T 和 RTST。 对任意字符串 x(RS)T，则 x 必定由 2 个子串 x1和 x2构成，即 x = x1x
10、2，其中，x1 RS，x2T。若 x1R，则 x1x2RTRTST；若 x1S，则 x1x2STRTST。总之 xRTST。 又对任意字符串 yRTST，则必定有 yRT 或 yST。即 y 必定由 2 个子串 y1和 y2构 成，即 y = y1y2，其中，y1R 或 y1S，y2T。即 y1 ST。从而 y(RS)T。 故(RS) T= RTST。于是(r + s)t = rt + st。即正规式的联接运算对加运算的右分配率 成立。 (f) (r*)* = r*。 证明 ：令正规式 r 表示字符串集合 R，则(r*)*和 r*分别表示字符串集合(R*)*和 R*。由 集合的联接闭包的性质可
11、知(R*)* = R*。故(r*)* = r*。 (g) ( +r)* = r*。 证明 ：令正规式 r 表示字符串集合 R。 由联接闭包的性质知 R*，故(R)* R*。所以( +r)* = r*。 (h) (r*s*)*= (r + s)*。 证明 ：令正规式 r 和 s 分别表示字符串集合 R 和 S。因为 R R*S*且 S R*S*，所以RS R*S*。于是(RS)* (R*S*)*。又对任意 x(R*S*)*，x 必定是由 R 和 S 中的符号串经过若干次联接之后形成的符号串，因而 x(RS)*。于是(R*S*)* (RS)*。所以 (r*s*)*= (r + s)*。6.对正规表
12、达式 r 和 s，证明下列等式成立或者不成立： (a) (r + s)* = r* + s*。 该等式不成立。 证明：令正规式 r 和 s 分别表示字符串集合 R 和 S。因为(rs)*均表示为所有由 r 和 s 中的符号串经过若干次联接的符号串，特别是其中包含了 r 中的符号串和 s 中的符号串相 互联接所构成的符号串。r*s*表示 r 的闭包与 s 的闭包的并集，其仅包含由 r 中的符号串 经过若干次联接的符号串和 s 中的符号串经过若干次联接的符号串，而不包含 r 中和 s 中 的符号串相互联接所构成的符号串。故(rs)*r*s*。所以该等式不成立。 (b) (rs + r)*r = r
13、(sr + r)*。 该等式成立。 证明：令正规式 r 和 s 字符串集合 r 和 s，则(rs + r)*r 和 r(sr + r)*分别表示字符串集合(rsr)*r 和 r(srr)*。对任意 x(rsr)*r，x 必定是以 r 中的字符串开头并且以 r 中的字符 串结尾。设 x = x1x2x3x4xn，其中 x1r 且 xnr。将 x 写成 x1(x2x3x4xn)，则 x1r 且x2x3x4xn(srr)*，即 xr (srr)*。同理可证对任意 yr(srs)*，亦有 y(rsr)*r。故 (rsr)*r =r(srr)*。所以该等式成立。 (c) (rs +r)*rs = (rr
14、*s)*。 该等式不成立。 证明：令正规式 r 和 s 字符串集合 r 和 s，则(rs + r)*rs 和(rr*s )*分别表示字符串集合(rsr)*rs 和(rr*s)*。设 r 和 s 中均不含有。于是rs，从而(rsr)*rs。而显然(rr*s) *。故(rsr)*rs (rr*s)*。所以该等式不成立。 (c) (r + s)*s = (r*s)*。 该等式不成立。 证明与(c)相类似。即等式的左侧不一定含有，而其右侧必定含有。 (d) s(rs + s)*r = rr*s(rr*s)*。 该等式不成立。 证明：令正规式 r 和 s 字符串集合 r 和 s，且令 r s。不妨设 w
15、r 且 ws。于是可以 有一个符号串ws(rss)*R，但是wrr*s(rr*s)*。因为等式左侧的符号串集合中都是以 r 中的符号串结尾的，而其右侧的符号串集合中都是以 s 中的符号串结尾的，所以该等式左 右两侧表示的符号串集合不相等。故该等式不成立。7.为下列正规表达式构造正规文法。 (1) (a | b)*a (a | b) 解：S Aa | AbA Ba B Ba | Bb | (2) (a | b)*a (a | b) (a | b) 解：S Aa | AbA Ba | Bb B Ca C Ca | Cb | (3) (a | b)*a (a | b) (a | b) (a | b)
16、 解：S Aa | AbA Ba | Bb B Ca | Cb C Da D Da | Db | 8.直接给出下述文法所对应的正规表达式S0A | 1B A1S | 1 B0S | 0 解：假设非终结符号 S、A、B 都分别代表一个正规式，则正规文法的产生式集合所代 表的就是关于正规式 S、A、B 的一个方程组。将文法“|”符号替换为正规式“+”符号，可得：S = 0A + 1B A = 1S + 1 B = 0S + 0 将 A 和 B 的方程式代入后可得： S = 0(1S+1)+1(0S+0) = 01(S+) + 10(S+) = (01+10)(S+)=(01+10)S+(01+10)。 根
