L9(x) = 1

計算理論初回の演習問題（定義や図の番号は配布資料のものを指します）
問 0.1 次の問題 L8 ，L9 を解く有限状態機械をそれぞれ作れ．図 6.4 の L3 を解く機械
4
が参考になるかもしれない．
{
L8 (x) =
真
偽

真
L9 (x) =
x に現れる b の個数が奇数であるとき
そうでないとき
x に現れる a の個数が 3 の倍数かつ
b の個数が奇数であるとき
偽そうでないとき
問 0.2 6.1.2 項末の問題 L5 を解く有限状態機械が存在しないことを示せ．
4
問 0.3 定理 6.3 の問題 L4 を解くチューリング機械を作れ．
4
問 0.4 6.3.1 項で，L5 は O(n2 ) 時間で解けるが，更に工夫をすれば O(n log n) 時間でも
7
解けると述べた．どうすればよいか．
問 0.5
2＋2
6.1.3 項や 6.2.2 項で，機械の定義を少し変えても問題を解く能力が変わらないと
述べた．それを証明するには，任意の問題 L に対し，一方の定義の下で L を解く機械が
あるならば，他方の定義の下でも L を解く機械が作れることを示すことになる．そのよ
うな証明を簡単な場合について考えてみよう．
（1）定義 6.4 や定義 6.6 ではテープ上の位置を各時刻に左か右へ動かすものとしてい
た．その場に留まることを許しても変わらないことを示せ．
（2）定義 6.4 や定義 6.6 では機械は入力文字列の左端から動作を始めるとしていた．右
端から始めるとしても変わらないことを示せ．
問 0.6
2＋2＋4
定理 6.5 を示そう．両方向有限状態機械 M が問題 L を解くとする．ただし前問
（2）を使い，M は入力文字列の右端から動作を開始するものとしておく．定義 6.4 と同様
に，M の状態集合を Q，そのうち受理状態 q受理と拒否状態 q拒否を除いたものを Q− ，文
字集合（空白以外）を Σ とする．Σ 上の文字列 x と状態 q ∈ Q− とに対し，[x](q) を次
で定める．x をテープ上に置いてその右端の位置で状態 q から M を動かし始めると，や
がて x の右端よりも右を
• 訪れるならば，その初めて訪れる時点での状態を [x](q) とする．
• 訪れることなく受理する場合，[x](q) = q受理．
• 訪れることなく拒否する場合，[x](q) = q拒否．
• 訪れることも終了することもない場合，[x](q) = ⊥．
1
つまり [x] は Q− から Q ∪ {⊥} への函数である．
（1）Σ の文字からなる文字列 x，x′ がもし [x] = [x′ ] を満すならば，Σ の任意の文字 σ
について，[xσ] = [x′ σ] が成り立つ．何故か．
（2）Σ の文字からなる文字列 x，x′ がもし [x] = [x′ ] を満すならば，M が x を受理す
るか否かと x′ を受理するか否かは一致する．何故か．
（3）定義 6.1 の有限状態機械であって L を解くものを作れ．Q− から Q ∪ {⊥} への函
数一つ一つを状態とするとよい（そのような函数は有限通りしかない）．遷移規則
や始状態，受理状態集合をどのように定めたらよいか．
問 0.7 配布した原稿（これはウェブには載せず，答案返却箱に何部か置いておきます）
1＋…
の誤りや改善点などを見つけて下さい（誤字脱字など軽微なものでよい）．誤り一つごと
に，最初に見つけた人に 1 点．
2

Download Report