Elements of the Theory of Computation (2ed)计算理论CH1 答案
1星 需积分: 13 100 浏览量
2018-10-09
22:30:39
上传
评论
收藏 50KB PDF 举报 
Undergraduate Course
ELEMENTS OF COMPUTATION THEORY College of Computer Science
Chapter 1 ZHEJIANG UNIVERSITY
Fall-Winter, 2006
P 46
1.7.4 Show each of the following.
(c) If a and b are distinct symbols, then {a, b}
∗
= {a}
∗
({b}{a}
∗
)
∗
.
(d) If Σ is an alphabet, e ∈ L
1
⊆ Σ
∗
and e ∈ L
2
⊆ Σ
∗
, then (L
1
Σ
∗
L
2
) = Σ
∗
.
Solution:
(c) It is obvious that {a}
∗
({b}{a}
∗
)
∗
⊆ {a, b}
∗
.
On the other hand, suppose that w ∈ {a, b}
∗
, then w = a
∗
or w = a
∗
ba
∗
ba
∗
· · · ba
∗
∈ {a}
∗
({b}{a}
∗
)
∗
.
(d) Suppose w ∈ (L
1
Σ
∗
L
2
). Then w = xyz, where x ∈ L
1
⊆ Σ
∗
, y ∈ Σ
∗
, z ∈ L
2
⊆ Σ
∗
.
Thus xyz ∈ (Σ
∗
)
∗
= Σ
∗
.
On the other hand, suppose w ∈ Σ
∗
. Then because e ∈ L
1
and e ∈ L
2
,
w = ewe ∈ (L
1
Σ
∗
L
2
).
1.7.6 Under what circumstances is L
+
= L
∗
− {e}?
Solution: L
+
= L
∗
− {e} exactly when e 6∈ L .
P 51
1.8.3 Let Σ = {a, b}. Write regular expressions for the following sets:
(c) All strings in Σ
∗
with exactly one occurrence of the substring aaa .
Solution: ((a ∪ aa ∪ b
∗
)b)
∗
aaa(bb
∗
(a ∪ aa ∪ b
∗
))
∗
.
1.8.5 Which of the following are true? Explain.
(a) baa ∈ a
∗
b
∗
a
∗
b
∗
(b) b
∗
a
∗
∩ a
∗
b
∗
= a
∗
∪ b
∗
资源评论
baidu_377763092019-10-18不是这本书的答案
