最終レポート課題

計算論最終レポート
提出締切:2016 年 8 月 8 日 (月)12:00
提出先 :[email protected]
1. 言語 ADFA , EDFA , ALLDFA , EQDFA を以下のように定義する．
ADFA = {⟨B, w⟩ | B は DFA であり，かつ，w を受理する }
EDFA = {⟨B⟩ | B は DFA であり，かつ，L(B) = ∅}
ALLDFA = {⟨B⟩ | B は DFA であり，かつ，L(B) = {0, 1}∗ }
EQDFA = {⟨B, C⟩ | B と C は DFA であり，かつ，L(B) = L(C)}
また，B1 , B2 , B3 , B4 をそれぞれ以下の状態遷移図をもつ DFA とする．
0
0,1
0
1
1
0
0,1
0
1
1
1
0
1
0
0,1
B1
B2
B3
0,1
B4
文字列 w1 , w2 ∈ {0, 1}∗ を w1 = 0101, w2 = 1011 と定義する．このとき，次の各問に答えよ．
(a) ⟨Bi , wj ⟩ ∈ ADFA となる組 ⟨Bi , wj ⟩ (i ∈ {1, 2, 3, 4}, j ∈ {1, 2}) をすべて挙げよ.
(b) ⟨Bi ⟩ ∈ EDFA となる Bi (i ∈ {1, 2, 3, 4}) をすべて挙げよ．
(c) ⟨Bi ⟩ ∈ ALLDFA となる Bi (i ∈ {1, 2, 3, 4}) をすべて挙げよ．
(d) ⟨Bi , Bk ⟩ ∈ EQDFA となる組 ⟨Bi , Bk ⟩ (i, k ∈ {1, 2, 3, 4}, i < k) をすべて挙げよ．
2. 上で定めた言語 ADFA , EDFA , ALLDFA , EQDFA が判定可能であることを示せ．
3. 任意の言語 L に対して，次の二つが等価であることを証明せよ．
(a) L および L が Turing 認識可能であること.
(b) L が判定可能であること.
4. 判定可能な言語の集まりは，以下の各演算に関して閉じていることを示せ．
(a) 和集合をとること
(b) 連結をとること
(c) スターをとること
(d) 補集合をとること
(e) 積集合をとること
5. 次の PCP ドミノの集まりに対するマッチをみつけよ．
{
b
a
ca
abc
,
,
,
ca
ab
a
c
}

Download Report