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

オートマトン・形式言語演習問題解答例
2016 年 10 月 4 日分
1.
(a) A ∪ B = {a, b, c, d}
(b) (A ∩ B) ∪ C = {a, b, e, f }
(c) A × C = {(a, e), (a, f ), (b, e), (b, f )}
(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. 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)
(2)
(3)
(4)
x ∈ R ∩ (S ∪ T )
仮定
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 ) は証明された．
5.
(a) Σ0 = {ϵ}
Σ2 = {aa, ac, ca, cc}
Γ0 = {ϵ}
Γ2 = {bb, bc, cb, cc}
(b) (Σ ∪ Γ)3 − (Σ3 ∪ Γ3 ) = {aab, aba, abb, abc, acb, baa, bab, bac, bba, bca, cab, cba}
(c) Σ∗ ∩ Γ∗ = {ci | i ≥ 0} = {ϵ, c, cc, . . .}

Download Report