オートマトンとチューリング機械.

Slides:



Advertisements
Similar presentations
0章 数学基礎.
Advertisements

和田俊和 資料保存場所 /2/26 文法と言語 ー正規表現とオートマトンー 和田俊和 資料保存場所
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
文法と言語 ー字句解析とオートマトンlexー
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
コンパイラ 2011年10月17日
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
5.チューリングマシンと計算.
5.チューリングマシンと計算.
計算の理論 II NP完全 月曜4校時 大月美佳.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
授業展開#11 コンピュータは 何ができるか、できないか.
8.クラスNPと多項式時間帰着.
東京工科大学 コンピュータサイエンス学部 亀田弘之
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
9.NP完全問題とNP困難問題.
データ構造と アルゴリズム 知能情報学部 新田直也.
コンパイラ 2012年10月15日
7.時間限定チューリングマシンと   クラスP.
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数
第2章 「有限オートマトン」.
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
シャノンのスイッチングゲームにおけるペアリング戦略について
計算の理論 II NP完全 月曜5校時 大月美佳 平成17年1月17日 佐賀大学理工学部知能情報システム学科.
文法と言語 ー字句解析とオートマトンlexー
形式言語の理論 5. 文脈依存言語.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
計算の理論 I ー 正則表現(今度こそ) ー 月曜3校時 大月 美佳.
形式言語とオートマトン Formal Languages and Automata 第4日目
計算の理論 II Turing機械 月曜4校時 大月美佳.
第3回 アルゴリズムと計算量 2019/2/24.
「情報科学」(4) データと計算(2) と 有限オートマトン.
計算の理論 II 言語とクラス 月曜4校時 大月美佳.
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
2007年度 情報数理学.
計算の理論 I ー閉包性ー 月曜3校時 大月 美佳.
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
15.1 文字列処理の基本 15.2 文字列処理用ライブラリ関数
JavaScriptを含んだHTML文書に対する データフロー解析を用いた構文検証手法の提案
第6章-2 計算のモデル オートマトン Turing 機械 計算可能性 1.
計算の理論 I 非決定性有限オートマトン(NFA)
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
5.チューリングマシンと計算.
計算の理論 I -プッシュダウンオートマトン-
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
プログラミング言語論 第10回 情報工学科 篠埜 功.
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
形式言語とオートマトン 第14回 プッシュダウンオートマトンと全体のまとめ
文法と言語 ー字句解析とオートマトンlexー
情報処理Ⅱ 2006年11月24日(金).
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
コンパイラ 2012年10月11日
計算の理論 I ε-動作を含むNFA 火曜3校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科.
非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.
形式言語とオートマトン Formal Languages and Automata 第5日目
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
情報処理Ⅱ 2005年11月25日(金).
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
計算の理論 II 多テープTuring機械 月曜4校時 大月美佳 平成16年11月29日 佐賀大学知能情報システム学科.
Presentation transcript:

オートマトンとチューリング機械

有限オートマトン

有限オートマトン 有限個の状態 入力文字列 状態遷移 現在の状態 初期状態 受理状態 有限個の文字 … アルファベット 入力文字と現在の状態に従って、 現在の状態をかえる。

状態遷移図 二進数を、0と1から 成る文字列として入力し、 3の余りを計算する 有限オートマトン 初期状態 1 1 1

言語 アルファベット 文字列(語) 言語(形式言語) 有限個の文字の集合 Σなどで表す。例:Σ={0,1} アルファベットに属する文字の有限列 例:0, 00, 1100, 0101 空列も文字列。εやλで表す。 文字列の全体をΣ* で表す。 言語(形式言語) 文字列の集合、すなわちΣ* の部分集合。 例:3で割り切れる二進数の全体

言語の認識装置としての 有限オートマトン 状態のいくつかを受理状態とする。 与えられた文字列に従って、 受理状態は複数あってもよい。 与えられた文字列に従って、 初期状態からはじめて状態遷移を繰り返す。 初期状態は一つ。 文字列を読み終わった直後の状態が 受理状態ならば、その文字列を受理。 有限オートマトンMが受理する 文字列の全体をL(M)と書く。 L(M)をMの受理言語という。

有限オートマトン 3で割り切れる二進数の 全体を受理する 有限オートマトン 初期状態 受理状態でもある。 1 1 1

有限オートマトン 初期状態 0と1を 奇数個ずつ 含む文字列を 受理する オートマトン 1 1 1 1

正則表現 言語を表す記法 文字列のパターンを表す。 例:0(10)*1 例:0(11+00)1 例:0(11+00)*1 0で始まり10が繰り返されて1で終わる文字列 そういう文字列からなる言語 例:0(11+00)1 0の次に11または00が来て、1で終わる文字列 例:0(11+00)*1

正則表現から有限オートマトンへ 正則表現⇒有限オートマトン 決定化 最小化 有限オートマトン⇒正則表現 正則言語 任意の正則表現に対して、その言語を受理する 非決定的な有限オートマトンが存在する。 決定化 非決定的な有限オートマトンは、受理言語が同じ 決定的なオートマトンに変換できる。 最小化 決定的なオートマトンは、 受理言語をかえずに状態数が最小化できる。 有限オートマトン⇒正則表現 正則言語

非決定的な有限オートマトン ε遷移: 文字を入力せずに 遷移できる。 ε 初期状態 1 1 1

非決定的な有限オートマトン 受理状態に至る遷移のしかたが 一つでもあればよい。 初期状態 1 1 1 1

決定的な有限オートマトン 初期状態 1 1 1

決定的な有限オートマトン 初期状態 1 1 1 1 1 1

状態数最小の有限オートマトン 初期状態 1 1 1 1 1

有限オートマトンの性質 受理言語の合併、交わり、補集合、連接、 閉包などに関して閉じている。 二つのオートマトンが受理する言語が同じか 任意のM1とM2に対して、 L(M1)∪L(M2)=L(M)となるMが存在する。 二つのオートマトンが受理する言語が同じか どうかを判定することができる。 数を数えられない:有限オートマトンの限界 例えば、0と1を同じ数だけ含む文字列のみを 受理する有限オートマトンは存在しない。

チューリング機械

チューリング機械 ヘッド テープ 有限状態制御部

チューリング機械の動作 有限状態制御部の状態と、 ヘッド上の文字の各組み合わせに対して、 という動作を定義。 ヘッドが書き込む文字(同じ文字をかけば無変化) 次の状態 (文字を書いた後に)ヘッドを 左右のどちらに動かすか、 動かさないか。 という動作を定義。 動作が一通りに定まらないものは、 非決定的なチューリング機械

チューリング機械の停止 停止状態を定めることもある。 次の動作が定義されなかったら停止。 場合によっては、停止しないこともある。

言語の認識装置としての チューリング機械 入力文字列をテープ上に書き込み、 ヘッドを最初の文字の上におき、 状態を初期状態にセットして、 書き込む前は空白文字が埋まっている。 テープには、入力文字列に現れる文字以外の 文字を書き込んでもよい。 入力アルファベット ⊂ テープ・アルファベット ヘッドを最初の文字の上におき、 状態を初期状態にセットして、 機械を走らせる。 停止したら、その文字列を受理。 受理状態において停止したら、 とすることもある。

int[][] nextstate = ...; int[][] chartowrite = ... int[][] nextmove = ...; int[] tape = ...; int state = ...; int head = ...; while (nextstate[state][tape[head]] >= 0) { int c = tape[head]; int s = state; state = nextstate[s][c]; tape[head] = chartowrite[s][c]; head += nextmove[s][c]; }

演習 0と1が同じ数だけ含む文字列のみを 受理するチューリング機械を定義せよ。 そのチューリング機械を、 Javaプログラムによって走らせてみよ。

チューリング機械と計算可能性

言語の認識装置として 入力アルファベット上の言語Lが、 チューリング機械Mによって 認識できるとき、その言語を 帰納的に可算という。 有限時間内にそのことがわかる。 Lに属していないときは、 Mは止まらないかもしれないので、 そのことはいつまでたっても わからないかもしれない。 以上のような認識が、 計算の限界である。 チャーチのテーゼ 入力文字列w 0 1 1 0 1 チューリング 機械 M 受理or不受理 (or非停止) w∈L w∈L

帰納的に可算 vs. 帰納的 入力アルファベット上の言語Lが、 常に停止するチューリング機械 Mによって認識できるとき、 その言語を帰納的いう。 Mを用いれば、与えられた文字列が Lに属しているとき、 有限時間内にそのことがわかる。 Lに属していないときも、 言語Lとその補集合がどちらも 帰納的に可算ならば、 L(およびその補集合)は 帰納的になる。 Mへの入力 0 1 1 0 1 チューリング 機械 M 受理or不受理 (常に停止する) w∈L w∈L

関数の実現機構として チューリング機械を用いて、 文字列をもらって文字列を返す関数を実現できる。 入力文字列をテープ上に書き込み、 チューリング機械を走らせる。 停止したら、テープ上の文字列を返す。 空白は無視する。 チューリング機械は止まらないかもしれないので、 いつも出力が得られるとは限らない。 部分関数 このような関数を部分帰納的関数という。 常に出力が得られるときは、帰納的関数という。 チューリング機械が常に止まる場合。

決定性と非決定性 計算可能性に関して(言語の認識装置として)、 決定的なチューリング機械と 非決定的なチューリング機械に 能力の差はない。 非決定的なチューリング機械が入力文字列を 受理するとは、入力文字列をテープ上に書き込み、 非決定的な動作を適切に選べば、 (受理状態で)停止すること。 任意の非決定的なチューリング機械に対して、 同じ言語を受理する決定的なチューリング機械が 存在する。

非決定的な チューリング機械 M M M 分身を作ると 思えばよい。 分身の一つが 受理すればよい。 M M 0 1 1 0 1 0 1 1 0 1 非決定的な チューリング機械 チューリング 機械 M 1 1 1 0 1 0 1 1 0 1 チューリング 機械 M チューリング 機械 M 1 0 1 0 1 1 1 1 0 1 分身を作ると 思えばよい。 分身の一つが 受理すればよい。 チューリング 機械 M チューリング 機械 M

万能チューリング機械 Mへの入力 Mのプログラム Mへの入力 万能 チューリング 機械 M 受理or不受理(or非停止) 0 1 1 0 1 s c z k q b 0 1 1 0 1 万能 チューリング 機械 チューリング 機械 M 受理or不受理(or非停止) 受理or不受理(or非停止)

万能チューリング機械と停止問題 万能チューリング機械は、 任意のチューリング機械Mのプログラムと Mへの入力に対して、Mをシミュレートできる。 Mが停止しないときは、 万能チューリング機械も停止しない。 Mが停止しないときも停止して、 Mの非停止を判定できるような 万能チューリング機械は存在するか。 プログラムが停止しないことを、 プログラムを実行せずに判定できるか? 答えは否。

チューリング機械と計算量

言語の認識の計算量 帰納的な言語を考える。 入力文字列に対して、 チューリング機械が停止するまでの 動作ステップ数が、入力文字列の長さに それを受理するチューリング機械は、 任意の文字列に対して必ず停止する。 入力文字列に対して、 チューリング機械が停止するまでの 動作ステップ数が、入力文字列の長さに どのように依存するか。 特に、入力文字列の長さnの「多項式」に比例した ステップ数(以下)で停止するか。 例えば、n2, n3...

P:多項式時間 帰納的な言語に対して、 それを受理する決定的な(常に停止する) チューリング機械で、 停止するまでの動作ステップ数が 入力文字列の長さの多項式で 抑えられるものが存在するとき、 その言語をPという。 もしくは、そのような言語のクラス(集まり)を Pという。

NP:非決定的多項式時間 帰納的な言語に対して、 それを受理する非決定的な(常に停止する) チューリング機械で、 停止するまでの動作ステップ数が 入力文字列の長さの多項式で 抑えられるものが存在するとき、 その言語をNPという。 動作の選び方をうまく選んだとき、 受理状態で停止するならば、 その入力文字列は受理されたとする。

PとNP もちろん、PはNPに含まれる。 PとNPは等しいか? Pである言語はNPでもある。 クレイ数学研究所が2000年に提示した 七つのミレニアム問題の一つ (賞金100万ドル)

NP完全 PとNPが等しいかどうかはわからないが、 PとNPが等しくないと仮定すると、 NP-Pに含まれることを示せる問題がある。 NPのうちで最も難しい問題 NPに属する任意の問題は、 多項式ステップでそのような問題に還元できる。 そのような問題をNP完全という。 逆に、NP完全の問題がPに属するならば、 NPに属するすべての問題がPに属する。

NP完全問題 ハミルトン経路問題 ブール式の充足可能性問題 グラフにハミルトン経路が存在するか。 ブール式は充足可能か。 指定された点から始まり指定された点に終わり、 すべての点をちょうど一回ずつ訪れる経路があるか。 グラフを適当なアルファベットの文字列として表現する。 ブール式の充足可能性問題 ブール式は充足可能か。 ブール変数の真偽を適当に定めると ブール式全体を真にできるか。 ブール式を適当なアルファベットの文字列として表現する。

関数の計算量 ハミルトン経路問題はNP完全である。 では、与えられたグラフに対して ハミルトン経路を求める問題は どのくらい難しいか? もし、ハミルトン経路が 決定的なチューリング機械により、 多項式時間で計算できるならば、 ハミルトン経路があるかどうかが 多項式時間で判定できてしまう。 従って、ハミルトン経路の計算も、 多項式ではできないはず。

PSPACE:多項式空間 帰納的な言語を認識するチューリング機械が、 停止するまでに、入力文字列の長さの 多項式で抑えられる空間(テープの量)しか 消費しないとき、その言語をPSPACEという。 決定的でも非決定的でも差はない。 NPを含む。 (真に含むかどうかはわからない。) P⊆NP⊆PSPACE