東京工科大学 コンピュータサイエンス学部 亀田弘之

Slides:



Advertisements
Similar presentations
形式言語とオートマトン2014 ー有限オートマトンー 第3日目
Advertisements

計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
5.チューリングマシンと計算.
5.チューリングマシンと計算.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
形式言語とオートマトン2011 ー有限オートマトンー 第3日目
スタック長の 特徴付けによる 言語の非DCFL性 証明
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数
第2章 「有限オートマトン」.
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
形式言語とオートマトン Formal Languages and Automata 第4日目
形式言語とオートマトン Formal Languages and Automata 第4日目
形式言語とオートマトン2008 ー有限オートマトンー
東京工科大学 コンピュータサイエンス学部 亀田弘之
文法と言語 ー字句解析とオートマトンlexー
形式言語とオートマトン2012 ー有限オートマトンー 第3日目
形式言語の理論 5. 文脈依存言語.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
形式言語とオートマトン Formal Languages and Automata 第4日目
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン2017 ー有限オートマトンー 第3日目
計算の理論 II 言語とクラス 月曜4校時 大月美佳.
計算の理論 II 時間量と領域量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳 平成15年6月2日 佐賀大学知能情報システム学科.
計算の理論 I 正則表現とFAとの等価性 月曜3校時 大月 美佳 平成15年6月16日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
2007年度 情報数理学.
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン2013 ー有限オートマトンー 第3日目
計算の理論 I 非決定性有限オートマトン(NFA)
5.チューリングマシンと計算.
計算の理論 I -プッシュダウンオートマトン-
計算の理論 I ー正則表現とFAの等価性ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン 第14回 プッシュダウンオートマトンと全体のまとめ
形式言語とオートマトン2015 ー有限オートマトンー 第3日目
文法と言語 ー字句解析とオートマトンlexー
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
Copyright 2002 守屋悦朗 オートマトンって? (Turing machine) (アニメーションで実行のこと)
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 2012年10月11日
形式言語とオートマトン2016 ー有限オートマトンー 第4日目
オートマトンって? (Turing machine).
計算の理論 I ε-動作を含むNFAと等価なDFA
非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.
形式言語とオートマトン Formal Languages and Automata 第5日目
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
計算の理論 II 多テープTuring機械 月曜4校時 大月美佳 平成16年11月29日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
Presentation transcript:

東京工科大学 コンピュータサイエンス学部 亀田弘之 形式言語とオートマトン2011 ー第8日目ー 東京工科大学 コンピュータサイエンス学部 亀田弘之

前回までの確認 有限オートマトン(FA) FAの定義と記述法 FAの種類 言語認識能力はどのFAでも同じ。 テープ上を一方向に動くヘッド (テープ上の記号を順次読みながら内部状態を遷移) M = <K, Σ, δ, q0, F>  (5つ組) 状態遷移図 様相(configuration) FAの種類 決定性FA(DFA) 非決定性FA(ε遷移のあるものとないもの) 言語認識能力はどのFAでも同じ。 正規言語(正規表現)を認識

有限オートマトンのイメージ(1) qk FAの概観 a1 a2 ai-1 ai an セル 入力記号 入力テープ ヘッド 内部状態 ・・・

有限オートマトンのイメージ(2) FA = ( K, Σ, δ, q0, F ) ただし、 K : 状態の集合( Kは有限集合) Σ : 入力アルファベット(Σは有限集合) δ : 状態遷移関数 δ: K×Σ∋( a, qi ) → qj ∈ K q0 : 初期状態 F : 最終状態の集合 ( F ⊆ K )

有限オートマトンのイメージ(2’) K = { r, s, t} , Σ= { a, b }, q0 = r, F ={ t }, δ : δ :  状態 入力 次の状態 r a s b t

有限オートマトンのイメージ(3) s a a b r b t a b

前回までの確認(2) 正規表現を認識するFAの存在とその構成法 正規表現αが与えられる。 正規表現αに対して、ε-NFA を構成する。 ε-NFA をDFAに書き換える。 DFAを状態数が最も少ない最簡形のDFA (Min-DFA)に書き換える。 Min-DFAをシミュレートするプログラムを作成する。 (注)上記5の説明および、最簡形DFA存在とその求め方を    与えるMyhill-Nerodeの定理の説明はまだしていません。

前回までの確認(3) Pushudown automaton(PDA) スタックの定義 PDAの定義と記述法 データ構造: ・配列(またはアレイ) ・リスト ・スタック ・キュー など Pushudown automaton(PDA) スタックの定義 スタックの構造と動作(pop-up と push-down) LIFO (Last-In First-Out) 型のメモリ PDAの定義と記述法 テープ上を一方向に動くヘッド+スタックメモリ (テープの記号を順次読み、スタック上の記号を順次  読み書きしながら内部状態を遷移) M = < K, Σ, Γ,δ, q0, Z0, F >  (7つ組) 状態遷移図 様相(configuration)

前回までの確認(4) スタックとPDAのイメージ図 Pop up Push down LIFO (Last In First Out) 最後に入れたものが最初に取り出される。

PDAのイメージ

前回までの確認 Pushdown automaton (PDA) PDAの種類 言語認識能力はNPDAの方が高い。 決定性プッシュダウンオートマトン Deterministic pushdown automaton (DPDA) 非決定性プッシュダウンオートマトン Nondeterministic pushdown automaton (NPDA) 言語認識能力はNPDAの方が高い。 FAは正規言語(正規表現)を認識 NPDAは文脈自由言語を認識 DPDAよりもNPDAの方が言語認識能力大 (注)“言語”そのものの話は後日お話します。

今日の内容 チューリングマシン (Turing Machine)

授業ではこの形式のものを扱います

TMの定義 TM M = < Q, Γ, Σ, δ, q0, B, F > (7つ組) Q:内部状態の集合 Γ:テープ記号の集合 Σ:入力記号の集合 ( Σ⊂ Γ ) δ:状態遷移関数 Q×Γ → Q×Γ×{ L, R } q0 :初期状態 ( q0 ∈ Q) B:ブランク記号 ( B ∈ Γ – Σ) F:最終状態の集合 ( F ⊂ Q )

TMのイメージ図

TM の例 例4.1(教科書p.90) 例4.2(教科書p.95) 例4.3(教科書p.96) 例4.4(教科書p.100) これらを順次確認していきましょう。

例4.1(教科書p.90) 入力文字列 aa aabb bbaa aaaabbbb

様相(Configuration)の導入 (q0, a1 a2 a3 ・・・ ai-1 ↓ai ai+1・・・ an )

例4.2(教科書p.95) M=<Q,Γ,Σ,δ,q0,B,F> Q={ q0, q1, q2, q3, qf } Σ={ a, b } Γ=Σ∪{a’,b’}∪{¢,$,B} δ: δ(q0,a)=(q1,a’,R) δ(q0,ab’=(q3,b’,R) δ(q1,a)=(q1,a,R)   δ(q1,b)=(q2,b’,L) δ(q1,b’)=(q1,b’,R) δ(q2,a)=(q2,a,L) δ(q2,a’)=(q0,a’,R) δ(q2,b’)=(q2,b’,L) δ(q3,b’)=(q3,b’,R) δ(q3,$)=(qf,$,L)

例4.3(教科書p.96) 言語 { anbnan | n>=1 } を受理するTM

例4.3(教科書p.96)

例4.4(教科書p.100) { ww | w ∈ { a, b }+ } を受理するTM

例4.5(教科書p.106) 2進数の和を計算するTM

今日はここまで 少しずつ復習をしてください。 個々のものは決して難しくはありません。 引き続き頑張りましょう。 来週は少し難しいです。 来週は授業評価アンケートを取りますので、PCを持参してください。