オートマトン・形式言語演習問題解答例

オートマトン・形式言語演習問題解答例
2015 年 10 月 6 日分
1.
(a) A ∪ B = {a, b, c, d, e, f }
(b) (A ∩ B) ∪ C = {a, b, c, d}
(c) A × C = {(a, c), (a, d), (b, c), (b, d)}
(d) (D − B) × C = ∅ × C = ∅
2.
(a) {∅, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}}
(b) {∅, {a}}
(c) {∅}
3. R+ = {(a, a), (a, b), (a, c), (a, d), (b, a), (b, b), (b, c), (b, d), (c, a), (c, b), (c, c), (c, d)}
R∗ = {(a, a), (a, b), (a, c), (a, d), (b, a), (b, b), (b, c), (b, d), (c, a), (c, b), (c, c), (c, d), (d, d)}
4. 集合の等価関係の定義より，(i) R ∩ (S ∪ T ) ⊆ R ∩ S ∪ R ∩ T ，および (ii) R ∩ (S ∪ T ) ⊇ R ∩ S ∪ R ∩ T
であることを示せばよい．
(i) まず，R ∩ (S ∪ T ) ⊆ R ∩ S ∪ R ∩ T を示す．このためには，集合の包含関係の定義より，
「 x ∈ R ∩ (S ∪ T )
ならば x ∈ R ∩ S ∪ R ∩ T 」を示せばよい． x ∈ R ∩ (S ∪ T ) を仮定して x ∈ R ∩ S ∪ R ∩ T であることを
示す．
(1) x ∈ R ∩ (S ∪ T )
(2)
(3)
(4)
x∈R
x ∈ S または x ∈ T
x ∈ R かつ x ∈ S ，または
仮定
(1) と積集合の定義より
(1) と，積集合と和集合の定義より
(2) と (3) より
x ∈ R かつ x ∈ T
(5) x ∈ R ∩ S ∪ R ∩ T
(4) と，和集合と積集合の定義より
以上により，R ∩ (S ∪ T ) ⊆ R ∩ S ∪ R ∩ T は証明された．
(ii) 次に，R ∩ (S ∪ T ) ⊇ R ∩ S ∪ R ∩ T を示す．集合の包含関係の定義より， x ∈ R ∩ S ∪ R ∩ T を仮定
して x ∈ R ∩ (S ∪ T ) であることを示せばよい．
(1) x ∈ R ∩ S ∪ R ∩ T
仮定
(2)
x ∈ R かつ x ∈ S ，または
x ∈ R かつ x ∈ T
(3) x ∈ R
(4) x ∈ S または x ∈ T
(5) x ∈ R ∩ (S ∪ T )
以上により，R ∩ (S ∪ T ) ⊇ R ∩ S
(1) と，和集合と積集合の定義より
(2) より
(2) より
(3) と (4)，和集合と積集合の定義より
∪ R ∩ T は証明された．
(i), (ii) ともに証明されたので，R ∩ (S ∪ T ) = R ∩ S ∪ R ∩ T は証明された．
5.
(a) Σ0 = {ϵ}
Σ2 = {aa, ab, ba, bb}
Γ0 = {ϵ}
Γ2 = {bb, bc, cb, cc}
(b) (Σ ∪ Γ)3 − (Σ3 ∪ Γ3 ) = {aac, abc, aca, acb, acc, bac, bca, caa, cab, cac, cba, cca}
(c) Σ∗ ∩ Γ∗ = {bi | i ≥ 0}

Download Report