- 前回のTh(M)の定義の訳が誤訳な予感。"the" collection of true sentences なので、trueとなるsentenceを全て集めたものがTh(M)。
- 脚注によると、modelは、interpretationとかstructureとかとも言うそうな。
- さて、"A DECIDABLE THEORY"。
- Theorem 6.12 Th(N, +) is decidable.
- これをやるまえに、問題1.31と1.32をやっておいた方がよさそうだ。第一章正規言語の問題だが。
- 問題1.31
- A^R = {w^R | w ∈ A}について、AがregularならA^Rもreguralを確認せよ、ということ。
- これは正規表現の帰納的な定義において、各ルールについてA^R版を考えられるので、まあ当然。
- A^R = {w^R | w ∈ A}について、AがregularならA^Rもreguralを確認せよ、ということ。
- 問題1.32
- Σ3 = {000, 001, 010, 011, 100, 101, 110, 111}
- B = {w ∈ Σ3* | 3n+1番目の文字をならべて数値と解釈した数と、3n+2番目を並べて数値と解釈した数との和が、3n+3番目を並べて数値と解釈した数に等しい。n={0,1,2,3,...}}
- 例：
001100110 ∈ B
001101 !∈ B - このBがregularであることを示せ。
- B^Rがregularであることを示す。そのregular expressionを具体的に構成する。
- まず、しらべてみる。
- 単一で要素たりえるもの。
000, 011, 101 - 二つで要素たりえるもの。(単二)
単一○単一
110001 - 三つで要素たりえるもの。(単三)
単二○単一
単一○単二
110 111 001
110 010 001
110 100 001 - 四つで要素たりえるもの。(単四)
単三○単一
単一○単三
単二○単二
110 111 111 001
110 010 111 001
110 100 111 001
110 111 010 001
110 010 010 001
110 100 010 001
110 111 100 001
110 010 100 001
110 100 100 001 - 規則性が見えてきた。
(000∪011∪101∪(110○hoge○001))*
で、hogeが、
(010∪100∪111)*
である。まとめると
(000∪011∪101∪(110○((010∪100∪111)*)○001))*
となる。(εをみとめないなら末尾を+に)
- まず、しらべてみる。
- しかし、足し算というのが正規言語に過ぎない、というのは結構すごいことだな。。。
- Σ3 = {000, 001, 010, 011, 100, 101, 110, 111}
- さて、本題。Theorem 6.12。
- 頭の中で考えてみたが、どうも集中できない、というかわからない。そこでメモをやる。
- 証明の方針検討。
- まず、言明Φを判定するアルゴリズムを考える、という目標設定。
- Φの表現を次のものにする。
Φ=Q1x1Q2x2...Qlxl[ψ]
ここでQ1...Qlはコンティフィア。ψはコンティフィアを含まず、変数x1...xlをもつ。 - さて、for (i = 0; i <= l; i++)的に、
Φ[i]=Q[i+1]x[i+1]Q[i+2]x[i+2]...Q[l]x[l] [ψ]
をつくる。するとi=0のとき、上のΦに等しいことがわかる。
Φ[0] = Φ
続けると、
Φ[1] = ΦからQ[1]x[1]をとったもの、
...
Φ[l-1] = Q[l]x[l] [ψ]
Φ[l] = ψ
となる。 - するとΦ[i]はi個の自由変数をもつ。
- で、a1,...,ai∈N、として、その自由変数に当てはめたものを、Φ[i](a1,...,ai)と表記する。
- で、for (i = 0; i <= l; i++)のそれぞれのiにおいて、
- このΦ[i](a1,...,ai)があるわけだが、
- これをtrueとする、a1,...,aiを認識するFA A[i]を構築する。
- 構築のプランは、
- まずA[l]を構築する。
- A[i]からA[i-1]が構築できることを示す。
- まずA[l]を構築する。
- というもの。
- 構築の結果、A[0]が得られれば、それはΦをtrueにする自由変数の入力を判定するものである。
- ところで、Φに自由変数はない。
- よって、Φが真ならば、A[0]はεを受理するはずである。偽ならば、拒否するはずである。
- このΦ[i](a1,...,ai)があるわけだが、
- まず、言明Φを判定するアルゴリズムを考える、という目標設定。
- 方針決定。
- ミソはAの構築であろう。そこを重点的に読む。
- Aの構築。
- A[i]のアルファベットは、問題1.32の拡張で、
Σ[i] = {[0...00], [0...01], [0...010], ... , [1...11]}.
で、それぞれの要素はi個の0or1を含むものとする。
また、
Σ[0] = {[]}.
とする。 - まず、A[l]を構成できるかどうか。
- さて、モデル(N,+)の話をしているのだから、ψというのは{∧, ∨, ¬, (,), R, x}からなり、RはPLUSであるものにすぎない。
- 一方で、問題1.32でみたように、PLUS(a,b,c)の入力たるa,b,cを認識するFAは構築可能である。
- ψを構成するには、PLUSをもとにして、前掲の論理演算で帰納的に組み立てていくしかない。
- ここで、PLUS(a,b,c)をみたすabcの組はtuple alphabetにおいて正規言語をなし、正規言語は、前掲の論理演算に関して閉じているので、結果得られる言語(ψに関する言語)も正規言語である。
- というわけでA[l]は構成できる。
- 次にA[i+1]からA[i]を構成できるかどうか。
- A[i+1]が存在すると仮定する。
- ところで、A[i+1]とは何か?
- Φ[i+1](a1,...,a[i+1])をtrueとする、a1,...,a[i+1]の表現たる言語を認識するFA。ここで、a1,...,a[i+1]の表現は、Σ[i+1] = {[0...0],[0...1],...,[1...1]}としたときのΣ[i+1]*をなし、Σ[i+1]*の要素の解釈はi+1-tupleのk番目の0or1を集めて連結したものがakであるというもの。
- 違う言葉でいうと、Φ[i+1]は自由変数をi+1個もつが、それぞれにa1,...,a[i+1]をいろいろあてはめていき、Φ[i+1]がtrueになるものだけを集めた言語。
- A[i+1]は、Σ[i+1]*を入力として、前項をみたすものだけ受理する。
- ところで、A[i+1]とは何か?
- A[i]を構成する。
- まず、Φ[i]とΦ[i+1]の関係は、これらの定義から、Φ[i] = ∃x[i+1]Φ[i+1]であるか、Φ[i] = ∀x[i+1]Φ[i+1]であるかのいずれかである。
- ∀xP(x) <=> ¬∃x¬P(x)だから、後者は、前者に帰着できる。よって、前者さえ構成できればよい。そこで前者の構成。
- まず、A[i]は状態として、A[i+1]のものと、新しい開始状態をもつ。
- そして、A[i]に入力[b1 ... b[i-1] b[i]]が与えられるたびに、A[i+1]の入力足りえる[b1 ... b[i-1] b[i] z]を想定する。
- ここで「想定する」とは、zが0or1であるとして非決定的に状態遷移する、ということ。
- で、すべての入力を処理し、非決定的な状態遷移を終えたときに、A[i+1]の受理状態にいるならば、それはその受理状態に辿りつくためのzの部分を連結して作ったa[i+1]にて、Φ[i]がtrueである、ということなので、そのときのa1,...,aiをA[i]は受理する。それ以外は拒否する。
- これでA[i]を構成できた。
- まず、A[i]は状態として、A[i+1]のものと、新しい開始状態をもつ。
- A[i]のアルファベットは、問題1.32の拡張で、
たかが、こつこつ。されど、こつこつ。
0 件のコメント:
コメントを投稿