故，原式得证
（3）(L1)*?L1
如果L1??,(L1)*???L1
如果L1??，假设L1?{a1,a2...an},n?1,
则L1?{?,a1,a2...an,a1a1,a1a2...a1an...}，而(L1)*?{?,a1,a2...an,a1a1,a1a2...a1an...} 故(L1)*?L1，原式得证
（4）(L1)??L1
如果L1??,(L1)????L1
如果L1??，假设L1?{a1,a2...an},n?1,
则L1?{a1,a2...an,a1a1,a1a2...a1an...}，而(L1)??{a1,a2...an,a1a1,a1a2...a1an...} 故(L1)??L1，原式得证
（5）(L1L2)L3?L1(L2L3)
??????********??(L1L2)L3={xy|x?L1,y?L2}L3?{xyz|x?L1,y?L2,z?L3}={x|x?L1}{yz|y?L2,z?L3}?L1(L2L3)
故，原式得证
（6）L1(L2?L3)?L1L2?L1L3
L1(L2?L3)?{x|x?L1}{y|y?L2或y?L3}?{xy|x?L1,y?L2或x?L1,y?L3}?{xy|x?L1,y?L2}?{xy|x?L1,y?L3}?L1L2?L1L3故，原式得证
21
（7）(L2?L)L31?L2L1?L3L1
(L2?L3)L1?{x|x?L2或x?L3}{y|y?L1}?{xy|x?L2,y?L1或x?L3,y?L1}{xy|x?L2,y?L1}?{xy|x?L3,y?L1}?L2L1?L3L1故，原式得证 （8）(L2?L)1*?(L2L1)*
*12n12n21**设?a?(L2?L),假设a?xx...x,则{x,x,...x}?L?L1
则xk?L2或xk?L1*，因
***xk?L2或xk?L1，当k=1,2,…n ******又因为??L2，??L1?L1?L1L2,L2?L1L2 故xk?L1L2,因此a?x1x2...xn?L1L2?(L2同理可证(L2综上(L2****?L)1*?(L2L1)*
**?L1)*?(L2L1)*
***?L)1?(L2L1)*
**故，原式得证 （9）(L1**{?})?L?1
当{?}?L1时，原式显然成立 当{?}?L1时，设L1?{x1,x2...xn}, 因为?x?x??x?(L1*?{?})*?{?,x1,x2...xn}*?{?,x1,x2...xn,x1x1,x1x2...x1xn...}
L1?{?,x1,x2...xn,x1x1,x1x2...x1xn...}
所以(L1?{?})**?L1
故，原式得证
22
（10）?*?{?} 因为，?0?{?} 所以，?*??0故，原式得证
（11）(L1????...?{?}
12?L?L?L)234134*?(L1L2L4L4)*
*12n12n2134****设?a?(L2?L?L?L),假设a?xx...x,则{x,x,...x}?L?L?L?L，
则xk?L2或xk?L1,或xk?L3,或xk?L4****xk?L2或xk?L1,xk?L3或xk?L4，当k=1,2,…n
又因为
??L2*,??L1*,??L3*,??L4*?L1*?L1*L2*L3*L4*,L2*?L1*L2*L3*L4*L3?L1L2L3L4,L4?L1L2L3L4**************
故xk?L1L2L3L4,因此
a?x1x2...xn?L1L2L3L4?(L1?L2?L3?L4)*?(L1L2L4L4)*
同理可证(L1综上(L1********?L?L?L)234*?(L1L2L4L4)*
********?L2?L3?L4)*?(L1L2L4L4)*
故，原式得证
（12）(L1L2)*?(L2L1)* 由8小题结论可以推得
****(L1L2)*?(L1?L2)*?(L2?L1)?(L2L1)*
故，原式得证
23
****1.31设L1，L2，L3，L4分别是?1，?2，?3，?4
上的语言，证明下列等式成立否
(段季芬)
（1）（L1L2）*=（L2L1）* 不成立
例如： L1={a}，L2={b}，则（L1L2）*=（ab）
*={?，ab,abab,ababab,….}
而（L2L1）*=（ba）
*={?,ba.baba,bababa,…...}
显然不等。 （2）L1+=L1+L1+ 不成立 例如： L1={0}，那么L1+=L1UL12UL13U。。。
={0，00，000，。。。}
而L1+L1+={00，000，
0000，。。。}，比L1+少基本项L1
可得知L1+L1+是L1+的子集 （3）L1*=L1*L1* 正确
因为L1*L1*=（L10UL1UL12UL13U。。。）
（L10UL1UL12UL13U。。。）
=（L10UL1UL12UL13U。。。）L10U
（L10UL1UL12UL13U。。。）L1U。。。。
=（L10UL1UL12UL13U。。。）
UAUBU。。。。
从观察可知A是
（L10UL1UL12UL13U。。。）的真子集，B 是A的真子集，
推知后面一项是前面的一项的真
子集，根据吸收规则
所以原式=L10UL1UL12UL13U。。。
=L1*
（1） （L1UL2）*=L2*UL1* 不正确
例如： L1={a}，L2={b}，左边={a,b}*={?,a,b,aa,ab,bb,…} 右边={?，b,bb,bbb,…}U{?,a,aa,aaa,….}={?,a,b,aa,bb,aaa,bbb, …} 没有a*b*项 肯定不等 （2） （L1L2UL1）*L1=L1（L2L1UL1）*
24
正确
（3） L2（L1L2UL2）*L1=L1L1*L2（L1L1*L2）
*
不正确
假设L1={a}，L2={b}，L2（L1L2UL2）*L1表示的语言肯定以b打头，而L1L1*L2（L1L1*L2）*
表示的语言肯定以a开头 （4） （L1+）*=（L1*）+=L1* 正确
（L1+）*=（L1UL12UL13U。。。）*={?，
2，
（L1UL12UL13U。。。），（L1UL12UL13U。。。）（L1UL12UL13U。。。）3。。。 }
由于（L1UL12UL13U。。。）n是（L1UL12UL13U。。。）n-1的子集（L1+）*表示的语言就是{ ?，（L1UL12UL13U。。。）}表示的语言即L1*，所以（L1+）*=L1*
（L1*）+=（L10L1UL12UL13U。。。）
+={（L10L1UL12UL13U。。。），（L10L1UL12UL13U。。。）2，（L10L1UL12UL13U。。。）3，。。。}
由于（L10UL1UL12UL13U。。。）n是
（L10UL1UL12UL13U。。。）n-1的子集
（L1*）+表示的语言就是
（L10UL1UL12UL13U。。。）表示的语言即L1*，所以（L1*）+
=L1*
所以（L1+）*=（L1*）+=L1*
（5） L1*L1+=L1+L1*=L1+ 正确
L1*L1+ =（L10UL1UL12UL13U。。。）U
（L1UL12UL13U。。。）
=（L10UL1UL12UL13U。。。）L1U
（L10UL1UL12UL13U。。。）L12U。。。 =（L1UL12UL13U。。。）U
（L12UL13UL14。。。）U。。。（后面的项都被第一项吸收）
=（L1UL12UL13U。。。）=L1+ 同理可证得L1+L1*=L1+
1.32 设??{0,1}，请给出上?的下列语言的形式表示。
25
(1) 所有以0开头的串。 解答：{0}{0,1}*。
(2) 所有以0开头，以1结尾的串。 解答：{0}{0,1}*{1}。
(3) 所有以11开头，以11结尾的串。 解答：{11}{0,1}*{11}。
(4) 所有最多有一对连续的0或者最多有一对连续的1的串。 解答：{01,1}*{?,00}{10,1}*?{10,0}*{?,11}{01,0}*。 (5) 所有最多有一对连续的0并且最多有一对连续的1的串。 解答：按照实际情况分成4类：
1) 只有一对连续的0： {01,1}*{00}{10,1}*。 2) 只有一对连续的1：{10,0}*{11}{01,0}*。 3) 没有连续的0并且没有连续的1：{10}*?{10}*。 4) 有一对连续的0和一对连续的1：
{01}*{00}{10}*{11}{01}*?{10}*{11}{01}*{00}{10}*。
(6) 所有长度为偶数的串。 解答：{0,1},n?1,2... （7）所有长度为奇数的串
解答：{0,1}
2n?12n,n=1,2 …
(8) 所有包含子串01011的串。 解答：{1,0}{01011}{1,0}。
(9) 所有包含3个连续0的子串。
解答：{0,1}*000{0,1}*
(10) 所有不包含3个连续0的串。 解答：{001，01，1}。 (11) 所有正数第10个字符是0的串。 解答：{0,1}{0}{0,1}。 (12) 所有倒数第10个字符是0的串。 解答：{0,1}0{0,1}。
26
*9***9*