形式语言第一章参考答案（蒋宗礼）

第一章参考答案

1.1请用列举法给出下列集合。

⑴ 你知道的各种颜色。

解：{红，橙，黄，绿，青，蓝，紫} ⑵ 大学教师中的各种职称。 解：{助教，讲师，副教授，教授} ⑶ 你所学过的课程。 解：{语文，数学，英语，物理，化学，生物，历史，地理，政治} ⑷ 你的家庭成员。 解：{父亲，母亲，妹妹，我} ⑸ 你知道的所有交通工具。 解：{汽车，火车，飞机，轮船，马车} ⑹ 字母表{a , b}上长度小于4的串的集合。 解：{a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb} ⑺ 集合{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中的元素为Ai（i=1,2,3,?），Ai也是集合，Ai中的元素

在1～10之间，并且和为10。根据集合元素的彼此可区分性，可以计算出Ai中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10（即10=1+2+3+4），这样，Ai中最多有4个元素。原因是：从最小的1开始，每次加入新的元素都只依次增加1，这样相加的和最小，要加到10，元素个数就最多。 求出最大的∣Ai∣＝4后，再求出元素个数为3，2，1的集合就可以了。 故A={{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

2.(1){x|0?x?100且x?z}(2){x|x?{a,b}*且|x|?4}(3){B|B?{1,2,3,4}}(4){L|L?{a,b}*}(5){x|x?2n?1,n?N}(6){(a,b)|a?b?10且a,b?[4,9]}(7){x|x?{0，1}*，且x中0的个数是1的个数的两倍}（8）{x|x?{0，1}*，且x中1的个数是10}(9){x|x?{0，1}*，且x中倒数第十个字符为1}（10）{A|?xi?A,xi?[1,10],i?[1,|A|],?xi=10}i?1|A||

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正确

2

1.6证明下列各题目 （02282081 刘秋雯）

1）A=B，iff A是B的子集且B是A的子集

证明：

充分条件： ∵A=B

则由集合相等的定义知 对于任何x∈A，有x∈B ∴A为B的子集 同理，B为A的子集 必要条件： ∵A为B的子集

∴ 对于任何x∈A，都有x∈B 又∵B为A的子集，

∴对于任何x∈B有，x∈A 由集合相等的定义知，A=B

2）如果A为B的子集，则|A|〈=|B|

证明：

A为B的子集，则对于任何x∈A 有x∈B,

∴存在一个集合C 使B=A∪C 且A∩C为空集 则|B|=|A|+|C| |C|〉=0 ∴|A|〈=|B|

3）如果A为B的真子集，则|A|〈=|B|

证明：

（1）当A为有穷集合时，因为A为B的真子集，且则对于任何x∈A 有x∈B,

且存在∈B的x，此x不∈A

∴存在一个非空集合C ， 使B=A∪C 且A∩C为空集 则|B|=|A|+|C| 且|C|〉=1 ∴|A|〈|B|

（2）当A为无穷集合，因为A为B的真子集，则B一定也为无穷集合，|A|＝∞，|B|＝∞

∴|A|=|B| 综合（1），（2）所述，|A|<=|B|

4）如果A是有穷集且A为B的真子集则|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不

3

∈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∈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∈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∈C.x不∈A ∴A为C的真子集

11）如果A=B，则|A|=|B|

证明：

A=B，则A与B所含元素相同 ∴|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). A

?B

4

= {1,3,5} = B (2).(A?B)?C ?{2,4,6}

= {1,3,5}

={1,2,3,4,5,6} = A (3).(A?B)?(U?C)= {1,3,5}

?{0,1,3,5,7,8,9}

={0,1,3,5,7,8,9} = C

(4).A-B-C

= {2,4,6} – {2,4,6} =?

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

?A ×? = ? (6).(A?B)?A?C?A

= {1,3,5}

?{0,7,8,9}

?{0,7,8,9}

= {0,1,3,5,7,8,9} = C

(7).A?B?A=A?B?C

=A?{(a,b)|(a?B,b?C)或(a?B,b?C)或(a?B,b?C)}

={(a,b,c)|(a?A,b?B,c?C)或(a?A,b?B,c?C)或(a?A,b?B,c?C)} (8).A= A= A?C

?B?(A?B)?C

?A?C ?C

= A

={1，2，3，4，5，6}

5

1．8 对论域U上的集合A、B、C，证明以下结论成立。 （02282047 吴贤珺）

⑴ A∪B＝B∪A 证：对任意的x，

x∈A∪B

?x∈A?x∈B ?x∈B?x∈A

?x∈B∪A

故A∪B?B∪A 且 B∪A?A∪B

则 A∪B＝B∪A。 ⑵ (A∪B)∪C＝A∪(B∪C) 证：对任意的x，

x∈(A∪B)∪C

?x∈(A∪B)?x∈C ?(x∈A?x∈B)?x∈C

?x∈A?x∈B?x∈C ?x∈A?(x∈B?x∈C) ?x∈A?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 iff B?A

证： ① 由B?A∪B及 A∪B＝A知 B?A。 ② 由B?A 知?x∈B, x∈A

则对任意的x，

x∈A∪B ?x∈A?x∈B ?x∈A

故 A∪B?A，又A?A∪B，所以 A∪B＝A。 综合①②得到 A∪B＝A iff B?A。

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

(a, b)∈A×(B∪C)

?a∈A?b∈(B∪C) ?a∈A?(b∈B?b∈C)

?(a∈A?b∈B)?( a∈A?b∈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)

6

证：对任意的有序对(b, a)，

(b, a)∈(B∩C)×A

?b∈(B∩C)?a∈A ?(b∈B?b∈C)?a∈A

?(b∈B?a∈A)?(b∈C?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)。

⑹ A×(B－C)＝(A×B)－(A×C) 证：对任意的有序对(a, b)，

(a, b)∈A×(B－C)

?a∈A?b∈(B－C) ?a∈A?(b∈B?b?C)

?(a∈A?b∈B)?( a∈A?b?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)。 需要说明的是：对于 (a, b)∈A×B?(a, b)?A×C ?(a∈A?b∈B)?( a∈A?b?C

本来，由(a, b)?A×C 只能得到 (a?A?b?C)。但是(a, b)∈A×B，故a∈A， 这样，必须b?C。

⑺ 如果 A?B，则2A?2B

证：对任意的C，C∈2A ?C?A

由于A?B，故C?B，则C∈2B，从而2A?2B。 ⑻ 2

A?B＝2A∩2B

证：对任意的C，

C∈2

A?B

?C?A∩B ?C?A?C?B ?C∈2A?C∈2B ?C∈2A∩2B

A?B 则 2

?2∩2且 2∩2?2

AB AB

A?B，故2

A?B＝2A∩2B。

⑼ │A∪B│≤│A│＋│B│

证：由容斥原理，│A∪B│＝│A│＋│B│－│A∩B│

7

① 当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∈B?b?C)?a∈A

?(b∈B?a∈A)?(b?C?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∈B?a∈A)?(b?C?a∈A)

本来，由(b, a)?C×A 只能得到 (a?A?b?C)。但是(b, a)∈B×A，故a∈A， 这样，必须b?C。 (11) 如果A?B，则B?A 证：对任意的x，x∈B?x?B

由于A?B，故x?A，即x∈A。因此，B?A。

(12) B＝A?A∪B＝U且A∩B＝Φ

证：① 由B＝A 以及A的定义知，A∪B＝A∪A＝U，A∩B＝A∩A＝Φ。

② 由A∩B＝Φ知，对任意的x∈B，x?A，即?x∈B，x∈A，故B?A。 又由A∪B＝U知，对任意的x∈A，x?A ，则x∈B，故A?B。 这样，B＝A。

综合①②得，B＝A?A∪B＝U且A∩B＝Φ。

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

x∈A?B

?x?(A∩B)

8

?x?A?x?B ?x∈A?x∈B ?x∈(A∪B)

则A?B?A∪B 且 A∪B?A?B 故A?B＝A∪B。

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

x∈A?B

?x?(A∪B) ?x?A?x?B ?x∈A?x∈B ?x∈(A∩B)

则A?B?A∩B 且 A∩B?A?B 故A?B＝A∩B。

1.9解答

(6) R={(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(b,c),(a,c)}

(9) R={(a,a),(b,b),(c,c),(d,d),(e,e), (a,b),(b,c),(a,c),(b,a),(c,b),(c,a)}

1.10 设R1和R2是集合{a,b,c,d,e}上的二元关系,其中,

R1={(a,b),(c,d),(b,d),(b,b),(d,e)}, R2={(a,a),(b,c),(d,c),(e,d),(c,a)} 求:R1R2,R2R1,R1+,R2+,R1*,R2*. 解答:

R1R2={(a,c),(c,c),(b,c),(d,d)}

R2R1={(a,b),(b,d),(d,d),(e,e),(c,b)}

R1+= {(a,b),(c,d),(b,d)(b,b),(d,e),(a,d),(a,e),(b.e),(c,e)} R2+={(a,a),(b,c),(d,c),(e,d),(c,a)(b,a),(d,a),(e,c),(e,a)}

R1*= R1+?{(a,a),(b,b),(c,c),(d,d),(e,e)} R2*= R2+?{(a,a),(b,b),(c,c),(d,d),(e,e)}

9

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

(1) R的传递闭包是{(a,b),(c,d),(b,d),(a,d)}.

(2) R的自反传递闭包是{(e,e),(a,a),(b,b),(c,c),(d,d),(a,b),(c,d),(b,d),(a,d)}.

1．12 设R1和R2是集合{a,b,c,d,e}上的二元关系，请证明下列关系。

(唐明珠 02282084)

(1) R1R2?R2R1。

证明：用反证法，假设R1R2?R2R1。

设R1?{(a,b),(c,d)},R2?{(b,c),(d,e)}。

则R1R2?{(a,c)},R2R1?{(b,d)}, 这与R1R2?R2R1相矛盾， 所以R1R2?R2R1。 (2) (R1R2)R3?R1(R2R3)。

证明：任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?(R1R2)R3 ??z((x,z)?R1R2?(z,y)?R3) z?{a,b,c,d,e} ??z((x,t)?R1?(t,z)?R2?(z,y)?R3)t?{a,b,c,d,e} ??z((x,t)?R1)??z((t,z)?R2?(z,y)?R3) ?(x,t)?R1?(t,y)?R2R3 ?(x,y)?R1(R2R3)

所以得证(R1R2)R3?R1(R2R3)。

(3) (R1?R2)R3?R1R3?R2R3。

证明：任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?(R1?R2)R3。 ??z((x,z)?R1?R2?(z,y)?R3) z?{a,b,c,d,e}

10

??z((x,z)?R1?(x,z)?R2?(z,y)?R3)

??z((x,z)?R1?(z,y)?R3)??z((x,z)?R2?(z,y)?R3) ?(x,y)?R1R3?(x,y)?R2R3 ?(x,y)?R1R3?R2R3

所以得证(R1?R2)R3?R1R3?R2R3

(4 ) R3(R1?R2)?R3R1?R3R2。

证明：任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?R3(R1?R2)。

??z((x,z)?R3?(z,y)?R1?R2) z?{a,b,c,d,e} ??z((x,z)?R3?(z,y)?R1?(z,y)?R2)

??z((x,z)?R3?(z,y)?R1)??z((x,z)?R3?(z,y)?R2) ?(x,y)?R3R1?(x,y)?R3R2 ?(x,y)?R3R1?R3R2

所以得证R3(R1?R2)?R3R1?R3R2。 (5) (R1?R2)R3?R1R3?R2R3。

证明：任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?(R1?R2)R3。 ??z((x,z)?R1?R2?(z,y)?R3) z?{a,b,c,d,e} ??z((x,z)?R1?(x,z)?R2?(z,y)?R3)

??z((x,z)?R1?(z,y)?R3)??z((x,z)?R2?(z,y)?R3) ?(x,y)?R1R3?(x,y)?R2R3 ?(x,y)?R1R3?R2R3

所以得证(R1?R2)R3?R1R3?R2R3。 (6) R3(R1?R2)?R3R1?R3R2。

11

证明：任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?R3(R1?R2)。

??z((x,z)?R3?(z,y)?R1?R2) z?{a,b,c,d,e} ??z((x,z)?R3?(z,y)?R1?(z,y)?R2)

??z((x,z)?R3?(z,y)?R1)??z((x,z)?R3?(z,y)?R2) ?(x,y)?R3R1?(x,y)?R3R2 ?(x,y)?R3R1?R3R2

所以得证R3(R1?R2)?R3R1?R3R2。

1.13 通常意义下的=是自然数集上的一个等价关系，请按照该等价关系给出自然数集的等价类 （02282075 冯蕊）

“=”关系将自然数集N分成无穷多个等价类：{0}，{1}，{2}，{3}，{4}，{5}，{6}，……

1.14.在什么样的假设下，人与人之间的“同乡关系”是等价关系。当“同乡关系”在给定的限定下成为等价关系时，它将所有的中国人分成什么样的等价类？

(吴玉涵 02282091) 答：假设出生在同一个省的关系为同乡关系。按照这样的同乡关系将中国人按照出生省份的不同划分出等价类。

1.16

?*上的二元关系RL 定义为：对任给的x,y??*，如果对于?z??*，

（1）对于?x?均有xz?L与yz?L，同时成立或者同时不成立，则xRLy。 (周期律 02282067)

证明：

?*

?*，故xRx，R

L

L

xz?L与xz?L显然是同时成立或同时不成立，对于?z?具有自反性。

对于?x,y??*，如果xRy, 故xz?L与yz?L同时成立或同时不成立，显

L

然故yz?L与xz?L同时成立或同时不成立，故yRLx, RL 具有对称性。

对于?x,y,p??*,如果xRy, yRp, 故xz?L与yz?L同时成立或同时不成

L

L

立，并且故yz?L与pz?L同时成立或同时不成立，故xz?L与pz?L同时成立或同时不

12

成立，故xRLp，故RL具有传递性。

综上，关系RL是在

?*上的等价关系。

（2）如果对于任给的x,y? 故对于?z? 对于?p??*，如果xRy，

L

?*，xz?L与yz?L同时成立或同时不成立，

L

?*,如果xzp?L,因为zp??*,又因为xRy, 故yzp?L，

因此，对于?p??*，?*,又因为xRy, 故yzp?L，

L

同理，可以证明如果xzp?L,因为zp?xzp?L与yzp?L同时成立或同时不成立，

故如果对于任给的x,y??*，如果xRy，则必有xzRyz。

L

L

综上，该关系的等价性和右不变性均得以证明。

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

设L是Σ上的一个语言,Σ*上的二元关系RL定义为:对任给的x,y?Σ*,如果对于?z?Σ*,均有xz?L与yz?L同时成立或者同时不成立,则xRLy.

根据上述定义可知, {0,1}*关于L所确定的等价关系RL的等价类有三个.

(1) ?x,y?{0n1m|n≥0,m>0},都有?z?Σ*,均有xz?L与yz?L同时成立或者同

时不成立

(只有当z?{1n|n≥0}的时候,才同时成立,否则不成立)

(2) ?x,y?{0n1m|n≥0,m=0},都有?z?Σ*,均有xz?L与yz?L同时成立或者同

时不成立

(只有当z?{0n1m|n,m≥0}的时候,才同时成立,否则不成立)

(3) ?x,y?{0n1m|n,m≥0},都有?z?Σ*,均有xz?L与yz?L同时成立或者同时

不成立

(无论z取何值,都不同时成立)

三个等价类为{0n1m|n≥0,m>0}{0n1m|n≥0,m=0}和除此之外的{0,1}*上的字符

1.18 RL确定的{0，1}*的等价分类为：

[10]={x10y|x,y∈{0,1}*}∪{1|n≥1}

n

[0]={01|m-n=0}={0n1n|n≥0} [1]={01|m-n=1}

mn

mn

13

[2]={01|m-n=2} . . .

[h]={01|m-n=h}

. . .

其中，n，m均为非负整数。

1.19.给出下列对象的递归定义 (02282072 褚颖娜)

1． n个二元关系的合成

(1) R1R2={(a,c)|?(a,b)? R1且?(b,c) ? R2}

(2) R1R2??Rn = {(d,g)|?(d,e)?R1R2?? Rn-1且?(f,g) ? Rn } 2． 无向图中路的长度

在无向图Ｇ中，若两顶点v1,v2之间存在一条无向边，则v1,v2是Ｇ的一条长位１的路 若v1,v2??vn-1为一条长度为k-1的路，且vn-1,vn存在一条无向边，则v1，v2??vn-1,vn为Ｇ的一条长度为k的路 3． 有向图中路的长度

在有向图Ｇ中，若两顶点v1,v2之间存在一条有向边，则v1,v2是Ｇ的一条长位１的路 若v1,v2??vn-1为一条长度为k-1的路，且vn-1,vn存在一条有向边，则v1，v2??vn-1,vn为Ｇ的一条长度为k的路 4． n个集合的乘积

S1?S2={(a,b)|a? S1且b? S2}

S1? S2??Sn={(d,e)|d? S1? S2??Sn-1且e? Sn } 5． 字母a的n次幂

(1) a0=1; (2) an=an-1a; 6． 字符串x的倒序

若x为单字符，则x的倒序是它本身

若x的倒序为y, 若x后跟一字符a, 则xa的倒序为ay; 7． 字符串x的长度

若x为空串?，则|x|=0;

若字符串x的长度为k,其xa或ax的长度为k+1 8． 自然数

0为自然数，

如果x为自然数，则x+1为自然数

mn

mn

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

14

1111n??????1?22?33?4n(n?1)n?1证明：(1)11（1）n=1时，?成立1?21?11111k（2）假设n=k时成立，即??????1?22?33?4k(k?1)k?111111当n?k?1时，??????1?22?33?4n(n?1)(n?1)(n?1?1)n1 =?n?1(n?1)(n?1?1)n(n?1?1)?1 =(n?1)(n?1?1)n?1 =（n?1）?1所以n?k?1时成立（3）由归纳原理，对任一n?N-?0?都成立

(2)当n?4时，2n?n2。证明：（1）当n=4时，2n?16?42成立（2）假设n=k时成立，即2k?k2当n?k?1时，2k+1?2?2k?2k222k2?（k+1）?k2?2k?1??k?1?2??k?1?2?????2由k?4知，2k2?（k+1）2所以，2k+1?（k?1），n?k?1时成立。

????（3）由归纳原理，?n?4?2n?n2

15

(3)当A，B为有穷集合时，A?B?AB。证明：设A?n，B?m（1）当n=0，m=0时，A?B?????0?AB 当n=0，m?0时，A?B???B?0?AB 当n?0，m?0时，A?B?A???0?AB（2）假设m?0，n=k时成立，即A?B?AB?mn?mk当n?k?1时，令A?A'??a?，A'??a???A?B??A'??a???B?A'?B??a??B?A'?B??a??B?mk?m?m(k?1)所以，n?k?1时，A?B?AB同理，当n?0，m=k成立时，m=k+1也成立（3）由归纳原理，当A，B为有穷集合时，A?B?AB成立。

（4）设A，B是有穷集合，则从A到B的映射有B个。证明：设A?n?1，B?m?1（1）当n=1，m=1时，从A到B的映射有BAA?1个，成立A（2）假设n=k时成立，即从A到B的映射有B?mk个A当n?k?1时，设A?A'??a?,A'??a???,A'?k从A到B的映射就是从A'??a?到B的映射，从A'到B的映射个数为B（3）由归纳原理，A，B是有穷集合，则从A到B的映射有B个。

A

?mk个，从?a?到B的映射个数为m个，所以从A'??a?到B的映射的个数为m?mk?mk?1(5)G?(V,E)为一个无向图，则?deg(v)?2E。v?V证明：（1）V?1时，E?0，?deg(v)?2E?0成立。v?V（2）设E=m，假设V?n?1时成立，即?deg(v)?2E?2mv?V当V?n?1时，设V?V'??v0?,V'??v0???,?deg(v)?2E'?2mv?V'

若v0与0?k?n个结点相连，则增加边数k，deg(v0)?k，对于n个结点增加度数也为k，所以，?deg(v)?2E'?2k?（2m?k）=2Ev?V（3）由归纳原理，G?(V,E)为一个无向图，则?deg(v)?2E。v?V

16

(6)G?(V,E)为一个有向图，则?ideg(v)??odeg(v)?E。v?Vv?V证明：（1）V?1时，E?0，?ideg(v)??odeg(v)?0?E成立v?Vv?V（2）设E=m，假设V?n?0时成立，即?ideg(v)??odeg(v)?E成立v?Vv?V当V?n?1时，设V?V'??v0?,V'??v0???，?ideg(v)??odeg(v)?E'?m

v?V'v?V'设ideg(v0)?p，odeg(v0)?q则?ideg(v)??ideg(v)?ideg(v0)??E'?q??p?Ev?Vv?V'v?V?odeg(v)??odeg(v)?odeg(v0)??E'?p??q?Ev?V'v?Vv?V（3）由归纳原理，当G?(V,E)为一个有向图时，?ideg(v)??odeg(v)?E

(7)一个高度为n?1的二元树的根结点到叶子的最大路长是n，该树最多含有2n个叶子证明：（1）高度为2时，最多有21?2个叶子，成立（2）假设高度为n+1时成立，即最多有叶子2n个当高度为n+2时，第n+1层上最多有结点2n个，则第n+2层上最多有叶子为2?2n?2n+1个（3）由归纳原理，高度为n+1的二元树最多含有2n个叶子

(8)根据1.4.3节中的相关定义，对字母表?中的任意字符串a，anam?an?m证明：（1）n=0,m=0时，a0a0??????a0成立（2）假设n=p，m=q时成立，即apaq?ap?q当n=p+1，m=q时，ap+1aq?a?aa?a?a?aaa?a?a?aa?aa??????p?1个q个p个q个p个q个

=ap?qa?ap?q+1同理有，n=p，m=q+1成立（3）由归纳原理，anam?an?m成立。

17

(9)对字母表?中的任意字符串x，x的前缀有x?1个。证明：（1）x=0，即x=?时，x的前缀只有它本身，有x?1?1个，成立（2）假设x=n时成立，即x的前缀有x?1?n?1个。当x=n+1时，设x=x'b,x'的前缀有n+1个。x中含有b的前缀只有一个，所以x的前缀有n+1+1个（3）由归纳原理，对字母表?中的任意字符串x，x的前缀有x?1个。

1．21下列集合中哪些是字母表。

(1 ) {1,2}。

(2 ) {a,b,c,…,z}。 (3 ) ?。

(4) {a,b,a,c}。

(5) {0，1，2，3，…,n,…}。 (6) {a,d,f}?{a,b,c,…,z}。 解答：字母表为 (1) (2) (6) (3)不满足字母表的非空性，(4)不满足字母表的可区分性，(5)是无穷集合不满足

字母表的有穷性。

22．设∑＝{a, b}，求字符串aaaaabbbba的所有前缀的集合，后缀的集合，真

前缀的集合，真后缀的集合。 （吴贤珺 02282047）

解：⑴ 前缀：{ε,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb,

aaaaabbbba}

⑵ 后缀: {ε,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba,

aaaaabbbba }

⑶ 真前缀: {ε,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb} ⑷ 真后缀: {ε,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba}

23．∑={aa,ab,bb,ba}，求字符串aaaaabbbba的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合。 （02282015 郭会）

解：

由前缀、后缀、真前缀、真后缀的集合可以有：

其前缀集合为：{ε,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba} 其真前缀集合为：{ε,aa,aaaa,aaaaab,aaaaabbb}

其后缀集合为：{ε,ba,bbba,abbbba, aaabbbba, aaaaabbbba } 其真后缀集合为：{ε,ba,bbba,abbbba, aaabbbba}

18

1.25抽象技术为什么对计算机技术特别重要？

（段季芬）

对于计算机技术方面的人来说，计算思维能力是必需的，这是学科本身决定的。计算机科学与技术

学科所要解决的根本问题是什么能被有效的自动化。现代计算机技术认为，要想有效的实现自动化， 必须经过抽象进行形式化。

1．26 为什么要求字母表示非空有穷集？ （唐明珠 02282084）

解答：字母表是非空有穷集合，由字母表中的元素连接而成的字符串叫做字母表上的

句子。假设字母表为空集，则字母表中唯一的元素就是?,而?不论如何组合，其组成的句子都为空，其研究就失去了意义，所以字母表要具有非空性。

1.27. 考虑一下,为什么要研究句子的前缀,后缀?

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

28．令∑＝{1, 0}，下列语言在结构上有什么样的特点？（吴贤珺 02282047）

⑴

nn

＝{01│n≥1}。 L1解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0或1的个数相等，且都不小于1个。 ⑵

Lnm＝{01│n, m≥1}。 2解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0或1的个数不一定相等，但都不小于1个。 ⑶

nnn＝{010│n≥1}。 L3解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每部分的0或1的个数相等，且都不小于1个。 ⑷

L4＝{0n1m0k│n, m, k≥1}。

解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每

部分的0或1的个数不一定相等，但都不小于1个。 ⑸

nnn＝{010│n≥0}。 L5 19

解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每

部分的0或1的个数相等，并且可以都为0。 ⑹

T

L6＝{xωx│x, ω∈??}。

解：该语言的每一个句子从前向后看和从后向前看时，有一部分是对称相等的。而且，

这对称相等的两个串中间一定有另外一个串。 ⑺

T

＝{x xω│x, ω∈?L7?}。

解：该语言的特点是在其句子中一定可以找到这样的一个串：该串是从句子的第一个字符开始的连续的串，且紧跟该串之后的连续一段字符串恰好是该串从后往前看是的那个串，而且这样的两个串之后一定还有另外一个字符串。 ⑻

L8＝{aωa│a∈?,ω∈??}。

解：该语言的每一个句子有这样的特点：该句子的第一个字符和最后一个字符都是0

或都是1，且该句子的长度不小于3。 ⑼

L9＝{ε,0,1,11,01,10,11,000,?}。

解：该语言的句子是所有由0和1构成的串，包括空串ε。 ⑽

L10＝{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 设L1,L2,L3,L4分别是?1,?2,?3,?4上的语言，证明下面的等式成立。

（1）L1?L2?L2?L1

212设?a?L1（2）L1?L,?a?L或a?L2312?a?L2或a?L1??a?L2?L1,故原式得证

3?(L?L)?(L?L)?L231

23设?a?L1?(L?L)?a?L或a?L或a?L20

??a?L1?(L2?L3)

故，原式得证

（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*

(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*

本文来源：https://www.bwwdw.com/article/8h93.html