決定可能
decidable
$ \alphaは計算可能である、または決定可能である、という $ x\in\alphaかどうかを、YES/NOで答えるプログラムが存在すること
任意の言語に対して、それを判定するチューリングマシンが存在する時、その言語を決定可能という 判定問題に、YES/NOの回答を与える計算手続き
関連
参考
以下を読んで意味がわからなければ、『計算理論の基礎 2』.iconの証明のアイディアを読めばいいmrsekut.icon
「DFAに対する受理問題」は「言語$ A_\mathrm{DFA}」として表現できる $ A_\mathrm{DFA}=\{\lang B,w\rang\}
$ Bは入力文字列$ wを受理するDFA
つまり、$ A_\mathrm{DFA}はDFAとそれ受理する文字列の組を符号化したものの全体を表す言語
$ A_\mathrm{DFA}は判定可能
これを証明するためには、$ A_\mathrm{DFA}を判定する以下のようなTM Mを考えればいい
チューリングマシンMは入力<B,w>に対して
1. 入力wに対してBをシミュレート
2. このシミュレーションが
受理状態で終了→受理
非受理状態で終了→拒否
こんな感じのTM Mが存在することを言えば、言語$ A_\mathrm{DFA}は判定可能だと言え、
ということは、DFAに対する受理問題も判定可能だと言える
ってこと？mrsekut.icon
$ A_\mathrm{NFA}=\{\lang B,w\rang\}
$ Bは入力文字列$ wを受理するNFA
$ A_\mathrm{NFA}は判定可能
証明は、上のDFAに対する受理問題の証明と同じことする
チューリングマシンTM Nを考える
1. NFA BをDFA Cに変換して入力の組<C, w>を作る
2. <C,w>を入力にしてTM Mを動作させる
3. Mが受理するならNも受理、そうでないならNも拒否する
じゃっかんメタだねmrsekut.icon
$ A_\mathrm{REX}=\{\lang R,w\rang\}
$ Rは文字列$ wを生成する正規表現
$ A_\mathrm{REX}は判定可能
正規表現はNFAに変換しDFAに変換できるので上の定理を適用できる
証明にはNFAの証明時に使ったチューリングマシンNを使う
有限オートマトンの言語に対する空性検査
空性検査とは与えらた集合が空集合かどうかを判定する
$ E_\mathrm{DFA}=\{\lang A\rang\}
$ AはDFAであり、$ L(A)=\phi
$ E_\mathrm{DFA}は判定可能
以下のようなTM Mを考えればいい
TM T=入力<A>に対して
1. Aの開始状態に印をつける
2. 新しく印をつける状態になくなるまで繰り返す
3. すでに印が付けられた任意の状態から1回の遷移ですすめるすべての状態に印をつける
4. 印がつけられた受理状態がないならば受理、そうでなければ拒否
2つのDFAが同じ言語を認識するかどうか決定することが判定可能か
$ \mathrm{EQ}_\mathrm{DFA}=\{\lang A,B\rang\}
A,BはDFAであり、$ L(A)=L(B)
$ \mathrm{EQ}_\mathrm{DFA}は判定可能
DFA C: AかBかどちらかには受理されるが両方には受理されない文字列のみ受理
$ L(C)=(L(A)\cap \overline{L(B)})\cup(\overline{L(A)}\cap L(B))
TM F=入力<A,B>に対して
1. DFA Cを構成する
2. 入力<C>に対して$ E_\mathrm{DFA}のTM Tを動作させる
3. Tが受理→受理、拒否→拒否
CFGが特定の文字列を生成するかどうかを決定するアルゴリズム
CFGの生成する言語が空であるかどうかを決定するアルゴリズム
$ A_\mathrm{CFG}=\{\lang G,w\rang\}
Gは文字列wを生成するCFG
$ A_\mathrm{CFG}は決定可能
TM S=入力<G,w>に対して
2. nをwの長さとしたときに(2n-1)ステップの全ての導出をリストにする。ただしn=0ならば代わりに1ステップの全ての導出をリストにする
3. これらの導出のいずれかがwを生成するなら受理、そうでなければ拒否
CFGの言語に対する空性判定
$ E_\mathrm{CFG}=\{\lang G\rang\}
GはCFGかつ$ L(G)=\phi
$ E_\mathrm{CFG}は決定可能
TM R＝入力<G>に対して
2. 新しく記しを付ける変数がなくなるまで繰り返す
3. Gが規則$ A\rightarrow U_1,U_2,\cdots U_kをもち、各々の文字$ U_1,U_2,\cdots U_kにすでに印がつけられているような任意の変数Aに印をつける
4. 開始変数に印がつけられていなければ受理、そうでなければ拒否
2つのCFGが同じ言語を生成するか
$ \mathrm{EQ}_\mathrm{CFG}=\{\lang G,H\rang|G,H:CFGかつL(G)=L(H)\}
CFGは補集合、積集合に閉じていない
$ \mathrm{EQ}_\mathrm{CFG}:判定不可能
全ての文脈自由言語(CFL)は判定可能
A: CFL
G: Aに対するCFG
Aを判定するTM $ M_Gを設計する
G: $ M_Gに組み込まれている
$ M_G=入力<G,w>に対して
1. 入力<G,w>に対して TM($ A_\mathrm{CFG}の)を動作させる
2. このマシンが受理→受理、 拒否→拒否
計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか？」である。この質問はやや難解なので、もう少し判り易く例を挙げる。まず、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。ref 参考