チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数

Slides:



Advertisements
Similar presentations
プログラミング言語について 情報工学科 篠埜 功 情報工学通論 2016 年 5 月 17 日. 2 1.プログラミング言語について.
Advertisements

計算の理論 I -言語とオートマトン- 月曜3校時 大月 美佳.
比較プログラム言語論 平成17年5月18日 森田 彦.
コンパイラ 2011年10月17日
チューリングマシン 2011/6/6.
言語処理系(4) 金子敬一.
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
5.チューリングマシンと計算.
5.チューリングマシンと計算.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
授業展開#11 コンピュータは 何ができるか、できないか.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
プログラミング言語論 第1回 導入 情報工学科 篠埜 功.
情報工学通論 プログラミング言語について 2015年 6月 16日 情報工学科 篠埜 功.
情報工学通論 プログラミング言語について 2013年 5月 28日 情報工学科 篠埜 功.
9.NP完全問題とNP困難問題.
データ構造と アルゴリズム 知能情報学部 新田直也.
プログラミング言語論 第1回 導入 情報工学科 篠埜 功.
コンパイラ 2012年10月15日
情報工学通論 プログラミング言語について 2014年 5月 20日 情報工学科 篠埜 功.
コンパイラ(9) 情報工学科5年 担当 河田 進.
7.時間限定チューリングマシンと   クラスP.
第2章 「有限オートマトン」.
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
形式言語の理論 5. 文脈依存言語.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
第二回 時制論理とリアルタイムリソース.
計算の理論 II Turing機械 月曜4校時 大月美佳.
第2回 状態モデルと 命令型言語(1) 担当:犬塚
オートマトンとチューリング機械.
文法と言語 ー文脈自由文法とLR構文解析2ー
計算の理論 II 言語とクラス 月曜4校時 大月美佳.
アドバンスドトピック 計算できるものと計算できないもの 2008年4月9日 神林 靖.
計算の理論 II 時間量と領域量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
計算の理論 II 計算量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳 平成15年6月2日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
2007年度 情報数理学.
チューリングマシン 0n1nを受理するチューリングマシン 入力テープ b b b b 状態遷移機械.
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
第6章-2 計算のモデル オートマトン Turing 機械 計算可能性 1.
文法と言語 ー文脈自由文法とLR構文解析ー
計算の理論 I 非決定性有限オートマトン(NFA)
5.チューリングマシンと計算.
計算の理論 I -プッシュダウンオートマトン-
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
形式言語とオートマトン 第14回 プッシュダウンオートマトンと全体のまとめ
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
Copyright 2002 守屋悦朗 オートマトンって? (Turing machine) (アニメーションで実行のこと)
コンパイラ 2012年10月11日
オートマトンって? (Turing machine).
計算の理論 I ε-動作を含むNFAと等価なDFA
計算の理論 I ε-動作を含むNFA 火曜3校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科.
非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.
文法と言語 ー文脈自由文法とLR構文解析2ー
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
計算の理論 II 多テープTuring機械 月曜4校時 大月美佳 平成16年11月29日 佐賀大学知能情報システム学科.
計算の理論 II 時間量と領域量 月曜4校時 大月美佳 2019/9/13 佐賀大学理工学部知能情報システム学科.
6.ユーザ定義型.
Presentation transcript:

チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数 初期状態 空白記号 受理状態の有限集合

チューリング機械の1ステップの動作(1) 有限制御部 のとき 状態 … …

有限制御部 に遷移する。 状態 … …

チューリング機械の1ステップの動作(2) 有限制御部 のとき 状態 … …

有限制御部 に遷移する。 状態 … …

初期様相 で定義されているステップから動作を開始して, 有限制御部 状態 … … …

以下,ステップを繰り返し,

動作停止時の様相 のとき, 入力語を受理する。 停止して, 有限制御部 状態 … …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

… …

受理状態で停止したので,M41は入力語aaaabbbbを受理する。 … …

なお, である。

受理状態に遷移したので, M42 は入力語 aaaabbbbaaaa を受理する。

である。