计算理论基础答案（部分）.pdf

发布时间：2022-06-12 发布人：admin 分类：说明书资料大小：0.32M 资料格式：pdf 举报版权申诉

5607445e-11a5-4aaf-ad9e-66d101a41b00.pdf-第1页.png

第1页 / 共19页

5607445e-11a5-4aaf-ad9e-66d101a41b00.pdf-第2页.png

第2页 / 共19页

5607445e-11a5-4aaf-ad9e-66d101a41b00.pdf-第3页.png

第3页 / 共19页

5607445e-11a5-4aaf-ad9e-66d101a41b00.pdf-第4页.png

第4页 / 共19页

5607445e-11a5-4aaf-ad9e-66d101a41b00.pdf-第5页.png

第5页 / 共19页

5607445e-11a5-4aaf-ad9e-66d101a41b00.pdf-第6页.png

第6页 / 共19页

5607445e-11a5-4aaf-ad9e-66d101a41b00.pdf-第7页.png

第7页 / 共19页

5607445e-11a5-4aaf-ad9e-66d101a41b00.pdf-第8页.png

第8页 / 共19页

文本预览

Exercises 1 1. If x∈{a,b}*, xa=ax, for some n, show x=an,n∈N. 2. Show that there are not strings x∈{a,b}* which make ax=xb. 3. Show 2 is an irrational. (reduction to absurdity) 4. P.29: 1.5.6 P.47: 1.7.2, 1.7.4 ; ; P.51: 1.8.1, 1.8.2, 1.8.3 P.52: 1.8.5 1、 If x∈{a,b}*, xa=ax, for some n, show x=an,n∈N. 证明：假设 xa=ax，而 x含字母 b。可将 x写成 x=anbu。则， anbua=aanbu=an+1bu，于是 bua=abu，矛盾。得证。 2、 Show that there are not strings x∈{a,b}* which make ax=xb. 证明：如果 x∈{a,b}*，且|x|=n，则 ax≠xb，需证明对于所有的 n∈N都是成立的。假设要证明对于所有的 m

②: suppose I<=n , (wn )R = (wR)n when I=n+1 (wi )R = (wn+1 )R = wR (wn )R = wR (wR)n =(wR)n+1=(wR)I 1.7.4: a: 任意个 e 的连接都是 e ,根据定义得 {e}*={e} b: 显然 L* ⊆ (L*)* 如果字符串 w∈ (L*)* 根据定义 w=w1 w2 w3 w4……wk wi ∈L* 同理 wi 由 L*中的字符串链接而成，w 也可以写成 L*中的字符串链接而成所以 w∈L* ，(L*)*⊆L* 所以 L* =(L*)* c: 根据定义易的 {a}*({b}{a}*)*⊆{a,b}* {a,b}*={a}*{b}*{a}*{b}* 而{a}*({b}{a}*)*= {a}*({b}{a}*)*({b}{a}*)*({b}{a}*)* {a}* ⊆ ({b}{a}*)*, 所以 {a}*{b}*{a}*{b}* ⊆ {a}*({b}{a}*)*({b}{a}*)*({b}{a}*)* 所以 {a,b}*⊆{a}*({b}{a}*)* 所以 {a,b}*={a}*({b}{a}*)* {b}* ⊆ ({b}{a}*)* d: 取 L1=e, L2=e 则 (L1Σ* L2)*= (Σ* ) * =Σ* 所以 Σ* ⊆ (L1Σ* L2)* 根据定义可得(L1Σ* L2)* ⊆ Σ* 所以 (L1Σ* L2)* =Σ* e: 题目有误 1.8.1： b 只出现一次，并且出现在结尾的字符串即 (a*) b (a): (a): (a): (a): (b): (c): (d): (a(a(a(a∪b)b)b)b)★ (a∪b)★ (a∪b)★ b★a(a∪b)★ 1.8.2: 1.8.2: 1.8.2: 1.8.2: 1.8.31.8.31.8.31.8.3 (a) b*(a∪b*)b*(a∪b*)b*(a∪b*)b* (b) (b*ab*ab*ab*)*∪b* (c) （（b*ab）*∪(b*aab) *）*aaa（（b*ab）*∪(b*aab) *）* 1.8.51.8.51.8.51.8.5 (a) true (b)(b)(b)(b) truetruetruetrue (c)(c)(c)(c) false false false false (d)(d)(d)(d) false false false false

Exercises 2 P.69 : 2.1.2, 2.1.3 P.73 : 2.2.1 P.74 : 2.2.2, 2.2.3 P.75 : 2.2.9 : a(ba)* : a* b : a((ab)∪(ba))*b ∪e :( (ba) ∪(ab)) *b (a(ba)*aa*b∪abbb *a∪b(ab) *bb *a∪baaa *b){a,b} * 2.1.2 (a) (b) (c) (d) (e) 2.1.3 (a): (b): (b): (b): (b): (c): (d): (f) :

2.2.12.2.12.2.12.2.1 (a): a, aa , e 会被接受 (b): e, ab, abab, aba 会被接受 2.2.22.2.22.2.22.2.2 ((((a): a* (b) (ab∪aba)* 2.2.32.2.32.2.32.2.3 (a): (b): ( c ):

(d): 2.2.9: 2.2.9: 2.2.9: 2.2.9: (a): (a): (a): (a): (b):

Exercises 2 P.69 : 2.1.2, 2.1.3 P.73 : 2.2.1 P.74 : 2.2.2, 2.2.3 P.75 : 2.2.9 2.1.2 (a) (b) (c) (d) (e) 2.1.3 (a): (b): (b): (b): (b): (d): : a(ba)* : a* b : a((ab)∪(ba))*b ∪e :( (ba) ∪(ab)) *b (a(ba)*aa*b∪abbb *a∪b(ab) *bb *a∪baaa *b){a,b} * (c): f: 2.2.12.2.12.2.12.2.1 (a): a, aa , e 会被接受 (b): e, ab, abab, aba 会被接受 2.2.22.2.22.2.22.2.2 ((((a): a* (b) (ab∪aba)* 2.2.32.2.32.2.32.2.3 (a):

(b): ( c ): 2.2.9: 2.2.9: 2.2.9: 2.2.9: (a): (a): (a): (a): (d): (b):

分享到：

赞收藏

资料库

计算理论基础答案（部分）.pdf

相关推荐

课程资源

热门标签

最新资料