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

オートマトン・形式言語演習問題
2016 年 10 月 4 日
1. 集合 A∼D を次のように与える．
A = {a, b}, B = {a, b, c, d}, C = {e, f }, D = ∅
このとき，次の集合を求めよ．
(a) A ∪ B
(b) (A ∩ B) ∪ C
(c) A × C
(d) (D − B) × C
2. 次の集合 A, B, C のべき集合をそれぞれ求めよ．
(a) A = {a, b, c}
(b) B = {a}
(c) C = ∅
3. 集合 X = {a, b, c, d} 上の関係 R = {(a, b), (b, c), (c, a), (a, d)} の推移閉包および反射推移
閉包を求めよ．
[関係の (反射) 推移閉包の定義] 集合 X 上の関係 S の推移閉包 S + と反射推移閉包 S ∗
は以下のように定義される関係である．
• S 0 = {(x, x) | x ∈ X}
• S i = {(x, z) | (x, y) ∈ S , (y, z) ∈ S i−1 }．ただし，i > 0．
∪
∪
• S + = i>0 S i , S ∗ = i≥0 S i
4. 集合 R, S , T に対して次の性質が成り立つことを定義より証明せよ．ただし，教科書
pp. 15∼16 にある定理 1.10 の証明と同様のやり方で証明せよ．
R ∩ (S ∪ T ) ⊆ (R ∩ S ) ∪ (R ∩ T )
[集合に関する定義] A, B を集合とする．
def
• A ⊆ B ⇔ x ∈ A ならば x ∈ B．
def
• x ∈ A ∪ B ⇔ x ∈ A または x ∈ B．
def
• x ∈ A ∩ B ⇔ x ∈ A かつ x ∈ B．
5. Σ = {a, c}, Γ = {b, c} である 2 つのアルファベット Σ, Γ に関して以下の問いに答えよ．
(a) Σ0 , Σ2 , Γ0 , Γ2 が表す言語をそれぞれ求めよ．
(b) (Σ ∪ Γ)3 − (Σ3 ∪ Γ3 ) が表す言語を求めよ．
(c) Σ∗ ∩ Γ∗ が表す言語を求めよ．

Download Report