形式语言与自动机理论-蒋宗礼-第一章参考复习资料.doc

第一章参考答案

1.1请用列举法给出下列集合。 （吴贤珺 02282047）
⑴ 你知道的各种颜色。
解：{红，橙，黄，绿，青，蓝，紫}
⑵ 大学教师中的各种职称。
解：{助教，讲师，副教授，教授}
⑶ 你所学过的课程。
解：{语文，数学，英语，物理，化学，生物，历史，地理，政治}
⑷ 你的家庭成员。
解：{父亲，母亲，妹妹，我}
⑸ 你知道的所有交通工具。
解：{汽车，火车，飞机，轮船，马车}
⑹ 字母表{a , b}上长度小于4的串的集合。
解：{}
⑺ 集合{1,2,3,4}的幂集。
解：{Φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},
{1,3,4},{2,3,4},{1,2,3,4} }
⑻ 所有的非负奇数。
解：{1,3,5,7,…}
⑼ 0～100的所有正整数。
解：{1,2,3,…,100}
(10) 1～10之间的和为10的整数集合的集合。
解：设所求的集合为A，集合A中的元素为（1,2,3,…），也是集合，中的元素在1～10之间，并且和为10。根据集合元素的彼此可区分性，可以计算出中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10（即10=1+2+3+4），这样，中最多有4个元素。原因是：从最小的1开始，每次加入新的元素都只依次增加1，这样相加的和最小，要加到10，元素个数就最多。
求出最大的∣∣＝4后，再求出元素个数为3，2，1的集合就可以了。
故{{10},{1,9},{2,8},{3,7},{4,6},{1,2,7},{1,3,6},{1,4,5},{2,3,5},{1,2,3,4}}

1.2 请用命题法给出下列集合

1.3 给出下列集合的幂集.（02282075 冯蕊）
(1) Φ
(2) {Φ}
(3) {Φ,{Φ}}
(4) {ε,0,00}
(5) {0,1}
解答:
(1) {Φ}
(2) {Φ,{Φ}}
(3) {Φ,{Φ},{{Φ}},{Φ,{Φ}}}
(4) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}
(5) {Φ,{0},{1},{0,1}}

1.4.列出集合{0，1，2，3，4}中 (褚颖娜 02282072)
（1） 所有基数为3的子集
{0，1，2}，{0，1，3}，{0，1，4}，{0，2，3，}，{0，2，4}，.{1，2，3}，{1，2，4}，{1，3，4}，{0，3，4}，{2，3，4}
（2） 所有基数不大于3的子集
Ф，{0}，{1}，{2}，{3}，{4}，{3，4}，{2，4}，{2，3}，{1，4}，{1，3}，{0，4}，{0，3}，{0，2}，{1，2}，{0，1}，{0，1，2}，{0，1，3}
{0，1，4}，{0，2，3，}，{0，2，4}，.{1，2，3}，{1，2，4}，{1，3，4}，{0，3，4}，{2，3，4}

1.5解答：
1、3、8、10、11、12、16正确

1.6证明下列各题目 （02282081 刘秋雯）
1）， A是B的子集且B是A的子集
证明：
充分条件：
∵
则由集合相等的定义知
对于任何x∈A，有x∈B
∴A为B的子集
同理，B为A的子集
必要条件：
∵A为B的子集
∴ 对于任何x∈A，都有x∈B
又∵B为A的子集，
∴对于任何x∈B有，x∈A
由集合相等的定义知，
2）如果A为B的子集，则〈
证明：
A为B的子集，则对于任何x∈A
有x∈B,
∴存在一个集合C 使∪C 且A∩C为空集
则
〉=0
∴〈
3）如果A为B的真子集，则〈
证明：
（1）当A为有穷集合时，因为A为B的真子集，且则对于任何x∈A
有x∈B,
且存在∈B的x，此x不∈A
∴存在一个非空集合C ， 使∪C 且A∩C为空集
则 且〉=1
∴〈
（2）当A为无穷集合，因为A为B的真子集，则B一定也为无穷集合，＝∞，＝∞
∴
综合（1），（2）所述，<
4）如果A是有穷集且A为B的真子集则〈
证明：
见上题证明（1）
5）如果A为B的子集，则对于任何x∈A，有x∈B
证明：
若A为B的子集，则由子集定义可知，对于任何x∈A，有x∈B
6）如果A是B的真子集，则对于任何x∈A，有x∈B，并且存在x∈B，但x不∈A
证明：
由真子集的定义可证
7）如果A为B的子集，B为C的子集，则A为C的子集
证明：
A为B的子集，B为C的子集
则对于任何x∈A，则x都∈B，
且，又对于任何y∈B，则y∈C，∴对于任何x∈A，x∈C
∴A为C的子集
8）如果A为B的真子集，B为C的真子集，则A为C的真子集
证明：
A为B的真子集，B为C的真子集
则对于任何x∈A，则x都∈B，
且，存在x∈B但次x不∈A，
又对于任何y∈B，则y∈C，存在y∈C但此y不∈B，
∴对于任何x∈A，x∈C，存在x∈不∈A
∴A为C的真子集
9）如果A为B的子集，B为C的真子集，则A为C的真子集
证明：
因为A为B的子集，B为C的真子集
则对于任何x∈A， x都∈B，且x都∈C
又对于任何y∈B，则y∈C，存在y∈C但此y不∈B，则y不∈A
∴对于任何x∈A，x∈C，存在x∈不∈A
∴A为C的真子集
10）如果A为B的真子集，B为C的子集，则A为C的真子集
证明：
A为B的真子集，B为C的子集
则对于任何x∈A，则x都∈B，
且存在x∈B但次x不∈A，
又对于任何y∈B，则y∈C
∴对于任何x∈A，x∈C，存在x∈不∈A
∴A为C的真子集
11）如果，则
证明：
，则A与B所含元素相同
∴
12）如果A为B的子集，B为C的真子集，或如果A为B的真子集，B为C的子集，则A为C的真子集
证明：证明见9，10

1.7 A = {1,2,3,4,5,6} B = {1,3,5} C = {2,4,6} U = {0,1,2,3,4,5,6,7,8,9}

(1).
= {1,3,5} = B
(2).
= {1,3,5}
={1,2,3,4,5,6} = A
(3).
= {1,3,5}
={0,1,3,5,7,8,9} =

(4)
= {2,4,6} – {2,4,6}
=

(5) × B × C ×
=
A × =

(6).
= {1,3,5}{0,7,8,9}{0,7,8,9}
= {0,1,3,5,7,8,9} =

(7).
=
=
=
(8).
=
=
=
={1，2，3，4，5，6}

1．8 对论域U上的集合A、B、C，证明以下结论成立。 （02282047 吴贤珺）
⑴ A∪B＝B∪A
证：对任意的x，
x∈A∪B
x∈∈B
x∈∈A
x∈B∪A
故A∪∪A 且 B∪∪B
则 A∪B＝B∪A。
⑵ (A∪B)∪C＝A∪(B∪C)
证：对任意的x，
x∈(A∪B)∪C
x∈(A∪B)x∈C
(x∈∈B)x∈C
x∈∈∈C
x∈A(x∈∈C)
x∈∈(B∪C )
x∈A∪(B∪C)
故(A∪B)∪C A∪(B∪C) 且 A∪(B∪C) (A∪B)∪C
则 (A∪B)∪C＝A∪(B∪C)。

⑶ A∪B＝A
证： ① 由∪B及 A∪B＝A知 。
② 由 知x∈B, x∈A
则对任意的x，
x∈A∪B
x∈∈B
x∈A
故 A∪，又∪B，所以 A∪B＝A。
综合①②得到 A∪B＝A 。

⑷ A×(B∪C)＝(A×B)∪(A∪C)
证：对任意的有序对(a, b)，
(a, b)∈A×(B∪C)
a∈∈(B∪C)
a∈A(b∈∈C)
(a∈∈B)( a∈∈C)
(a, b)∈A×B(a, b)∈A×C
(a, b)∈(A×B)∪(A×C)
故A×(B∪C) (A×B)∪(A∪C) 且 (A×B)∪(A∪C) A×(B∪C)
则 A×(B∪C)＝(A×B)∪(A∪C)。

⑸ (B∩C)×A＝(B×A)∩(C×A)
证：对任意的有序对(b, a)，
(b, a)∈(B∩C)×A
b∈(B∩C)a∈A
(b∈∈C)a∈A
(b∈∈A)(b∈∈A)
(b, a)∈B×A(b, a)∈C×A
(b, a)∈(B×A)∩(C×A)
故(B∩C)×A (B×A)∩(C×A) 且 (B×A)∩(C×A) (B∩C)×A
则 (B∩C)×A＝(B×A)∩(C×A)。

⑹ A×(B－C)＝(A×B)－(A×C)
证：对任意的有序对(a, b)，
(a, b)∈A×(B－C)
a∈∈(B－C)
a∈A(b∈)
(a∈∈B)( a∈)
(a, b)∈A×B(a, b)A×C
(a, b)∈(A×B)－(A×C)
故A×(B∪C) (A×B)∪(A∪C) 且 (A×B)∪(A∪C) A×(B∪C)
则 A×(B∪C)＝(A×B)∪(A∪C)。
需要说明的是：对于 (a, b)∈A×B(a, b)A×C
(a∈∈B)( a∈ 本来，由(a, b)A×C 只能得到 ()。但是(a, b)∈A×B，故a∈A，
这样，必须。

⑺ 如果 ，则2A2B
证：对任意的C，C∈2A
由于，故，则C∈2B，从而2A2B。

⑻ 2＝2A∩2B
证：对任意的C，
C∈2
∩B

C∈2AC∈2B
C∈2A∩2B
则 2 2A∩2B 且 2A∩2B 2，故2＝2A∩2B。

⑼ │A∪B│≤│A│＋│B│
证：由容斥原理，│A∪B│＝│A│＋│B│－│A∩B│
① 当A∩B≠Φ时，│A∪B│＜│A│＋│B│
② 当A∩B＝Φ时，│A∪B│＝│A│＋│B│
由①②知│A∪B│≤│A│＋│B│。

(10) (B－C)×A＝(B×A)－(C×A)
证：对任意的有序对(b, a)，
(b, a)∈(B－C)×A
b∈(B－C)a∈A
(b∈)a∈A
(b∈∈A)(∈A)
(b, a)∈B×A(b, a)C×A
(b, a)∈(B×A)－(C×A)
故 (B－C)×A (B×A)－(C×A) 且 (B×A)－(C×A) (B－C)×A
则 (B－C)×A＝(B×A)－(C×A)。
需要说明的是：对于 (b, a)∈B×A(b, a)C×A
(b∈∈A)(∈A) 本来，由(b, a)C×A 只能得到 ()。但是(b, a)∈B×A，故a∈A，
这样，必须。
(11) 如果，则
证：对任意的x，x∈
由于，故，即x∈。因此，。

(12) B＝A∪B＝U且A∩B＝Φ
证：① 由B＝ 以及的定义知，A∪B＝A∪＝U，A∩B＝A∩＝Φ。
② 由A∩B＝Φ知，对任意的x∈B，，即x∈B，x∈，故B。
又由A∪B＝U知，对任意的x∈， ，则x∈B，故B。
这样，B＝。
综合①②得，B＝A∪B＝U且A∩B＝Φ。

(13) ＝∪
证：对任意的x，
x∈
x(A∩B)

x∈x∈
x∈(∪)
则∪ 且 ∪
故＝∪。

(14) ＝∩
证：对任意的x，
x∈
x(A∪B)

x∈x∈
x∈(∩)
则∩ 且 ∩
故＝∩。

1.9解答
(6) {(),(),(),(),(),(),(),()}
(9) {(),(),(),(),(), (),(),(),(),(),()}

1.10 设R1和R2是集合{}上的二元关系,其中,
R1={(),(),(),(),()}, R2={(),(),(),(),()}
求1R22R1121*2*.
解答:
R1R2={(),(),(),()}
R2R1={(),(),(),(),()}
R1 {(),(),()(),(),(),(),(),()}
R2{(),(),(),(),()(),(),(),()}
R1*= R1+{(),(),(),(),()}
R2*= R2+{(),(),(),(),()}

1.11.设{(),(),()}是集合{}上的二元关系,求: （敖 雪 峰）
(1) R的传递闭包. (2) R的自反传递闭包.
解:
(1) R的传递闭包是{(),(),(),()}.
(2) R的自反传递闭包是{(),(),(),(),(),(),(),(),()}.

1．12 设和是集合{}上的二元关系，请证明下列关系。
(唐明珠 02282084)
(1) 。
证明：用反证法，假设。
设。
则
这与相矛盾，
所以。
(2) 。
证明：任取(),其中，使得

所以得证。

(3) 。
证明：任取(),其中，使得。

所以得证

(4 ) 。
证明：任取(),其中，使得。

所以得证。
(5) 。
证明：任取(),其中，使得。

所以得证。
(6) 。
证明：任取(),其中，使得。

所以得证。

1.13 通常意义下的=是自然数集上的一个等价关系，请按照该等价关系给出自然数集的等价类 （02282075 冯蕊）
“=”关系将自然数集N分成无穷多个等价类：{0}，{1}，{2}，{3}，{4}，{5}，{6}，……

1.14.在什么样的假设下，人与人之间的“同乡关系”是等价关系。当“同乡关系”在给定的限定下成为等价关系时，它将所有的中国人分成什么样的等价类？ (吴玉涵 02282091)
答：假设出生在同一个省的关系为同乡关系。按照这样的同乡关系将中国人按照出生省份的不同划分出等价类。

1.16 上的二元关系 定义为：对任给的，如果对于，均有与，同时成立或者同时不成立，则。 (周期律 02282067)
证明：
（1）对于
与显然是同时成立或同时不成立，对于，故， 具有自反性。
对于，如果, 故与同时成立或同时不成立，显然故与同时成立或同时不成立，故, 具有对称性。
对于,如果, , 故与同时成立或同时不成立，并且故与同时成立或同时不成立，故与同时成立或同时不成立，故，故具有传递性。
综上，关系是在上的等价关系。
（2）如果对于任给的，如果，
故对于，与同时成立或同时不成立，
对于,如果,因为,又因为, 故，
同理，可以证明如果,因为,又因为, 故， 因此，对于，与同时成立或同时不成立，
故如果对于任给的，如果，则必有。
综上，该关系的等价性和右不变性均得以证明。

1.17 设{0,1}*上的语言{01m≥0},请给出{0,1}*关于L所确定的等价关系的等价类.

设L是Σ上的一个语言,Σ*上的二元关系定义为:对任给的ÎΣ*,如果对于"zÎΣ*,均有ÎL与ÎL同时成立或者同时不成立,则.
根据上述定义可知, {0,1}*关于L所确定的等价关系的等价类有三个.
(1) "Î{01m≥0>0},都有"zÎΣ*,均有ÎL与ÎL同时成立或者同时不成立
(只有当zÎ{1≥0}的时候,才同时成立,否则不成立)
(2) "Î{01m≥00},都有"zÎΣ*,均有ÎL与ÎL同时成立或者同时不成立
(只有当zÎ{01m≥0}的时候,才同时成立,否则不成立)
(3) "Ï{01m≥0},都有"zÎΣ*,均有ÎL与ÎL同时成立或者同时不成立
(无论z取何值,都不同时成立)
三个等价类为{01m≥0>0}{01m≥00}和除此之外的{0,1}*上的字符

1.18 确定的{0，1}*的等价分类为：
[10]={x10∈{0,1}*}∪{1≥1}
[0]={0m10}={0n1≥0}
[1]={0m11}
[2]={0m12}
.
.
.
[h]={0m1}
.
.
.
其中，n，m均为非负整数。
1.19.给出下列对象的递归定义 (02282072 褚颖娜)
1． n个二元关系的合成
(1) R1R2={()|$()Î R1且$() Î R2}
(2) R1R2…… = {()|$()ÎR1R2…… 1且$() Î }
2． 无向图中路的长度
在无向图Ｇ中，若两顶点v12之间存在一条无向边，则v12是Ｇ的一条长位１的路
若v12……1为一条长度为1的路，且1存在一条无向边，则v1，v2……1为Ｇ的一条长度为k的路
3． 有向图中路的长度
在有向图Ｇ中，若两顶点v12之间存在一条有向边，则v12是Ｇ的一条长位１的路
若v12……1为一条长度为1的路，且1存在一条有向边，则v1，v2……1为Ｇ的一条长度为k的路
4． n个集合的乘积
S1´S2={()Î S1且bÎ S2}
S1´ S2……{()Î S1´ S2……1且eÎ }
5． 字母a的n次幂
(1) a0=1;
(2) -1a;
6． 字符串x的倒序
若x为单字符，则x的倒序是它本身
若x的倒序为y, 若x后跟一字符a, 则的倒序为;
7． 字符串x的长度
若x为空串e，则0;
若字符串x的长度为k,其或的长度为1
8． 自然数
0为自然数，
如果x为自然数，则1为自然数

1.20.使用归纳法证明下列各题。 (吴玉涵 02282091)

1．21下列集合中哪些是字母表。
(1 ) {1,2}。
(2 ) {,…}。
(3 ) 。
(4) {}。
(5) {0，1，2，3，…,…}。
(6) {}{,…}。
解答：字母表为 (1) (2) (6)
(3)不满足字母表的非空性，(4)不满足字母表的可区分性，(5)是无穷集合不满足字母表的有穷性。

22．设∑＝{a, b}，求字符串的所有前缀的集合，后缀的集合，真前缀的集合，真后缀的集合。 （吴贤珺 02282047）
解：⑴ 前缀：{ε,
}
⑵ 后缀: {ε,
}
⑶ 真前缀: {ε}
⑷ 真后缀: {ε}

23．∑={}，求字符串的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合。 （02282015 郭会）
解：
由前缀、后缀、真前缀、真后缀的集合可以有：
其前缀集合为：{ε}
其真前缀集合为：{ε}
其后缀集合为：{ε, , }
其真后缀集合为：{ε, }

1.25抽象技术为什么对计算机技术特别重要？ （段季芬）
对于计算机技术方面的人来说，计算思维能力是必需的，这是学科本身决定的。计算机科学与技术
学科所要解决的根本问题是什么能被有效的自动化。现代计算机技术认为，要想有效的实现自动化，
必须经过抽象进行形式化。

1．26 为什么要求字母表示非空有穷集？ （唐明珠 02282084）
解答：字母表是非空有穷集合，由字母表中的元素连接而成的字符串叫做字母表上的句子。假设字母表为空集，则字母表中唯一的元素就是不论如何组合，其组成的句子都为空，其研究就失去了意义，所以字母表要具有非空性。

1.27. 考虑一下,为什么要研究句子的前缀,后缀?
解: 形式语言是研究自然语言和人工语言的数学工具，只研究组成规则，不研究语义。而我们将语言看做句子的集合,句子看做字母按照一定规则组成的字符串,故主要根据规则的形式区分语言类,大部分问题都可转化为判定某个句子是否属于某个语言的问题.而这就要求从一个句子的结构出发,而一个整体的句子在结构上将其划成几个部分,对于我们的研究会有很大的帮助.事实上研究句子的前缀,后缀,也就是为了将句子结构进行有意识的划分而更加方便的研究句子,看其是否符合某个形式语言的组成规则.

28．令∑＝{1, 0}，下列语言在结构上有什么样的特点？（吴贤珺 02282047）
⑴＝{0n1n│n≥1}。
解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0或1的个数相等，且都不小于1个。
⑵＝{0n1m│n, m≥1}。
解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0或1的个数不一定相等，但都不小于1个。
⑶＝{0n1n0n│n≥1}。
解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每部分的0或1的个数相等，且都不小于1个。
⑷＝{0n1m0k│n, m, k≥1}。
解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每部分的0或1的个数不一定相等，但都不小于1个。
⑸＝{0n1n0n│n≥0}。
解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每部分的0或1的个数相等，并且可以都为0。

⑹＝{xω│x, ω∈}。
解：该语言的每一个句子从前向后看和从后向前看时，有一部分是对称相等的。而且，这对称相等的两个串中间一定有另外一个串。
⑺＝{x ω│x, ω∈}。
解：该语言的特点是在其句子中一定可以找到这样的一个串：该串是从句子的第一个字符开始的连续的串，且紧跟该串之后的连续一段字符串恰好是该串从后往前看是的那个串，而且这样的两个串之后一定还有另外一个字符串。
⑻＝{aωa│a∈,ω∈}。
解：该语言的每一个句子有这样的特点：该句子的第一个字符和最后一个字符都是0或都是1，且该句子的长度不小于3。
⑼＝{ε,0,1,11,01,10,11,000,…}。
解：该语言的句子是所有由0和1构成的串，包括空串ε。
⑽＝{0,1,00,01,10,11,000,…}。
解：该语言的句子是所有由0和1构成的串，不包括空串ε。

1.29设L1，L2，L3，L4分别是Σ1,Σ2,Σ3,Σ4上的语言，能否说L1，L2，L3，L4都是某个字母表Σ上的语言？如果能，请问这个字母表Σ是怎么样的？
（刘钰 02282083）
答：能 Σ=Σ1∪Σ2∪Σ3∪Σ4

1.30 设分别是上的语言，证明下面的等式成立。
（1）
设故原式得证
（2）
设
故，原式得证

（3）
如果
如果，假设
则，而
故，原式得证

（4）
如果
如果，假设
则，而
故，原式得证

（5）

故，原式得证

（6）
故，原式得证

（7）

故，原式得证

（8）
设
则，因此，当1,2,…n
又因为
故因此
同理可证
综上
故，原式得证

（9）
当时，原式显然成立
当时，设
因为

所以
故，原式得证

（10）
因为，
所以，
故，原式得证

（11）
设
则，因此，当1,2,…n
又因为
故因此
同理可证
综上
故，原式得证

（12）
由8小题结论可以推得

故，原式得证

1.31设L1，L2，L3，L4分别是Є1，Є2，Є3，Є4上的语言，证明下列等式成立否 (段季芬)
（1）（L1L2）*=（L2L1）*
不成立
例如： L1={a}，L2={b}，则（L1L2）*=（）*={Є，,….}
而（L2L1）*=（）*={Є,…...}
显然不等。
（2）L111+
不成立
例如： L1={0}，那么L111213U。。。={0，00，000，。。。}
而L11{00，000，0000，。。。}，比L1+少基本项L1
可得知L11+是L1+的子集

（3）L1*1*L1*
正确
因为L1*L1*=（L1011213U。。。）（L1011213U。。。）
=（L1011213U。。。）L10U（L1011213U。。。）L1U。。。。
=（L1011213U。。。）。。。。
从观察可知A是（L1011213U。。。）的真子集，B 是A的真子集，
推知后面一项是前面的一项的真子集，根据吸收规则
所以原式1011213U。。。1*
（1） （L12）*2*1*
不正确
例如： L1={a}，L2={b}，左边={}*={Є,…}
右边={Є，,…}U{Є,….}={Є, …}
没有a*b*项
肯定不等
（2） （L1L21）*L11（L2L11）*
正确

（3） L2（L1L22）*L11L1*L2（L1L1*L2）*
不正确
假设L1={a}，L2={b}，L2（L1L22）*L1表示的语言肯定以b打头，而L1L1*L2（L1L1*L2）*
表示的语言肯定以a开头
（4） （L1+）*=（L1*）1*
正确
（L1+）*=（L11213U。。。）*={Є，（L11213U。。。），（L11213U。。。）2，（L11213U。。。）3。。。 }
由于（L11213U。。。）n是（L11213U。。。）1的子集（L1+）*表示的语言就是{ Є，（L11213U。。。）}表示的语言即L1*，所以（L1+）*1*
（L1*）（L10L11213U。。。）{（L10L11213U。。。），（L10L11213U。。。）2，（L10L11213U。。。）3，。。。}
由于（L1011213U。。。）n是（L1011213U。。。）1的子集
（L1*）+表示的语言就是（L1011213U。。。）表示的语言即L1*，所以（L1*）1*
所以（L1+）*=（L1*）1*

（5） L1*L111*1+
正确
L1*L1+ =（L1011213U。。。）U（L11213U。。。）
=（L1011213U。。。）L1U（L1011213U。。。）L12U。。。
=（L11213U。。。）U（L121314。。。）U。。。（后面的项都被第一项吸收）
=（L11213U。。。）1+
同理可证得L11*1+

1.32 设，请给出上的下列语言的形式表示。
(1) 所有以0开头的串。
解答：。
(2) 所有以0开头，以1结尾的串。
解答：。
(3) 所有以11开头，以11结尾的串。
解答：。
(4) 所有最多有一对连续的0或者最多有一对连续的1的串。
解答：。
(5) 所有最多有一对连续的0并且最多有一对连续的1的串。
解答：按照实际情况分成4类：
1) 只有一对连续的0： 。
2) 只有一对连续的1：。
3) 没有连续的0并且没有连续的1：。
4) 有一对连续的0和一对连续的1：
。
(6) 所有长度为偶数的串。
解答：
（7）所有长度为奇数的串
解答：{0,1}1,2 …
(8) 所有包含子串01011的串。
解答：。
(9) 所有包含3个连续0的子串。
解答：{0,1}*000{0,1}*
(10) 所有不包含3个连续0的串。
解答：{001，01，1}。
(11) 所有正数第10个字符是0的串。
解答：。
(12) 所有倒数第10个字符是0的串。
解答：{0,1}0{0,1}。