オートマトン・形式言語 演習問題 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) Σ∗ ∩ Γ∗ が表す言語を求めよ.
© Copyright 2024 ExpyDoc