決定可能
decidable
判定可能とも言う (?)
\alphaは計算可能である、または決定可能である、という
x\in\alphaかどうかを、YES/NOで答えるプログラムが存在すること
任意の言語に対して、それを判定するチューリングマシンが存在する時、その言語を決定可能という
判定問題に、YES/NOの回答を与える計算手続き
こっちでは、「実効的方法」と訳されている
関連
参考
>#WIP
有限オートマトンに関する計算問題
有限オートマトンが文字列を受理するか、空かどうか
2つの有限オートマトンが等価かどうかを検査するアルゴリズム
以下を読んで意味がわからなければ、
の証明のアイディアを読めばいい
決定性有限オートマトンに対する受理問題
「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に対する受理問題も判定可能だと言える
ってこと？
非決定性有限オートマトンに対する受理問題
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も拒否する
じゃっかんメタだね
正規表現が与えられた文字列を生成するかどうか
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>に対して
1. Gをチョムスキー標準形の等価な文法に変換する
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>に対して
1. 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
参考