形式言語とオートマトン

講義URL:
http://www.kono.cis.iwate-u.ac.jp/~yamanaka/Lecture/Automata/index.html
形式言語とオートマトン
第1回演習問題解答例
山中克久
練習問題
練習問題1
A = {a1,a2, … , an} の冪集合をP(A)とする．
P(A)の要素数 |P(A)| はいくつになるか?
練習問題2
A = {a1,a2, … ,an}，B = {b1,b2, … ,bm} とする．
AとBの直積の要素数 |A×B| はいくつになるか?
練習問題3
S がある無限集合 U の有限部分集合であれば，
S の補集合 T は無限集合であることを示せ
背理法で証明しましょう
練習問題
練習問題1
A = {a1,a2, … , an} の冪集合をP(A)とする．
P(A)の要素数 |P(A)| はいくつになるか?
Ans. |P(A)| = 2n
練習問題2
A = {a1, a2, … , an}，B = {b1, b2, … , bm} とする．
AとBの直積の要素数 |A×B| はいくつになるか?
Ans. |A×B| = nm
練習問題3（答え）
主張
S がある無限集合 U の有限部分集合であれば、
S の補集合 T は無限集合である
背理法
証明：
T を有限集合と仮定
状況整理：
U: 無限
S: 有限
T: 無限?
の仮定
ある整数 m に対して
|T| = m と書ける
また，ある整数 n に対して
矛盾
|S| = n と書ける
|U| = |S| + |T| = m + n
■

Download Report