計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)

Slides:



Advertisements
Similar presentations
計算の理論 I -言語とオートマトン- 月曜3校時 大月 美佳.
Advertisements

文法と言語 ー字句解析とオートマトンlexー
コンパイラ 2011年10月17日
5.チューリングマシンと計算.
5.チューリングマシンと計算.
計算の理論 II NP完全 月曜4校時 大月美佳.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
計算の理論 I -講義について+αー 月曜3校時 大月美佳.
コンパイラ 2012年10月15日
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数
第2章 「有限オートマトン」.
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
形式言語とオートマトン Formal Languages and Automata 第4日目
形式言語とオートマトン Formal Languages and Automata 第4日目
形式言語とオートマトン2008 ー有限オートマトンー
計算の理論 II NP完全 月曜5校時 大月美佳 平成17年1月17日 佐賀大学理工学部知能情報システム学科.
文法と言語 ー字句解析とオートマトンlexー
文法と言語 ー字句解析とオートマトンlexー
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
計算の理論 I 正則表現 火曜3校時 大月 美佳 平成16年6月8日 佐賀大学知能情報システム学科.
計算の理論 I ー 正則表現(今度こそ) ー 月曜3校時 大月 美佳.
計算の理論 I 正則表現 月曜3校時 大月 美佳 平成15年6月9日 佐賀大学知能情報システム学科.
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
形式言語とオートマトン Formal Languages and Automata 第4日目
計算の理論 II Turing機械 月曜4校時 大月美佳.
計算の理論 I -言語とオートマトン- 月曜3校時 大月 美佳.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
計算の理論 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年度 情報数理学.
計算の理論 I ー閉包性ー 月曜3校時 大月 美佳.
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I ー正則表現とFAの等価性 その1ー
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
計算の理論 I 反復補題 月曜3校時 大月 美佳 平成15年7月14日 佐賀大学知能情報システム学科.
計算の理論 I 非決定性有限オートマトン(NFA)
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
5.チューリングマシンと計算.
計算の理論 I -プッシュダウンオートマトン-
計算の理論 I ー正則表現とFAの等価性ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
ミニテスト12解答 月曜3校時 大月 美佳.
計算の理論 I -講義について+αー 月曜3校時 大月美佳 平成31年5月18日 佐賀大学理工学部知能情報システム学科.
文法と言語 ー字句解析とオートマトンlexー
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
計算の理論 I 反復補題 火曜3校時 大月 美佳 平成16年7月13日 佐賀大学知能情報システム学科.
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
計算の理論 I ε-動作を含むNFAと等価なDFA
計算の理論 I ε-動作を含むNFA 火曜3校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科.
非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.
形式言語とオートマトン Formal Languages and Automata 第5日目
計算の理論 I -講義について+αー 火曜3校時 大月美佳 平成31年8月23日 佐賀大学理工学部知能情報システム学科.
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
計算の理論 II 多テープTuring機械 月曜4校時 大月美佳 平成16年11月29日 佐賀大学知能情報システム学科.
計算の理論 II 時間量と領域量 月曜4校時 大月美佳 2019/9/13 佐賀大学理工学部知能情報システム学科.
計算の理論 I 最小化 月曜3校時 大月 美佳 平成15年6月23日 佐賀大学知能情報システム学科.
Presentation transcript:

計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA) 月曜3校時 大月 美佳

開始の数から終了の数までこの関数に代入していって足し合わせる 前回のテストについて (Σの読み方) 開始の数から終了の数までこの関数に代入していって足し合わせる 終了の数 (この場合はnまで) 変数 開始の数 (この場合は0から) ⇒ 0からnまでf(i)に代入したものを足し合わせる 例:

前回のテストについて (Σと帰納法) 注意点 基底を間違えない 終了位置の展開を間違えない 基底は開始位置から始めること 前回のテストについて (Σと帰納法) 注意点 基底を間違えない 基底は開始位置から始めること 1から始めたので0が足りない人多数 終了位置の展開を間違えない n=k+1と置きながらkで展開している人多数 ○ ×

前回のテストについて (問題 a その1) を帰納法により証明する。 開始の数 1. i=0 のとき(基底) , 両辺とも0となり成り立つ。

前回のテストについて (問題 a その2 ) 2. n=k (k≧0)のとき が成り立つとする。 n=k+1 のとき 仮定より 終了の数

前回のテストについて (問題 b その1) を帰納法により証明する。 開始の数 1. i=0 のとき(基底) , 両辺とも0となり成り立つ。

前回のテストについて (問題 b その2 ) 2. n=k (k≧0)のとき が成り立つとする。 n=k+1 のとき 仮定およびaより 終了の数 となり n=k+1 のときも確かに成り立つ。(以下略)

その他コメント 略した部分もちゃんと書くように aの演繹的解き方 帰納法で大事なのは始めと終わりの把握 掲示板はまだ… ここで席替え 「1と2から与式は成り立つ。」とか aの演繹的解き方 ひっくり返して足す 帰納法で大事なのは始めと終わりの把握 掲示板はまだ… ここで席替え

前回の復習 有限状態系のモデル FAの定義 M = (Q, Σ, δ, q0, F) ⇒有限オートマトン (FA) 例:自動販売機、エレベータ、渡船 FAの定義 M = (Q, Σ, δ, q0, F)

FAの定義式 M = (Q, Σ, δ, q0, F) 有限個の状態の集合 Q (有限の)入力アルファベットΣ 入力記号によって引き起こされる状態遷移 遷移関数δ:Q×ΣからQへの写像 初期状態 q0∈Q 最終状態の集合 F⊆Q

FAの模式図 テープ ⇒記号列Σ*(Σ上のすべての記号列の集合) 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 有限 制御部 アルファベット 0, 1 Σ 遷移関数δ 有限状態系 qx q0 qz qy qf 最終状態の集合 q0, qx, qy, qz, qf Q F 状態の集合 初期状態

FAの例 (p.21 図2.2の定義式) M=(Q, Σ, δ, q0, F) Q = { q0, q1, q2, q3 } even-even even-odd odd-even odd-odd M=(Q, Σ, δ, q0, F) Q = { q0, q1, q2, q3 } Σ= { 0, 1 } F = { q0 } δ(q, a)→ 入力:a 1 q0 q2 q1 q3 状態:q

受理について 入力列xを有限オートマトンMで受理する 受理言語=正則集合(正則) → M = (Q, Σ, δ, q0, F)のとき δ(q0, x) ∈F ⇒要するに、xのとおり遷移すると最終状態になるということ 受理言語=正則集合(正則) 受理される入力記号列の集合 正則=正規

今日の新しいこと 非決定性有限オートマトン (nondeterministic finite automaton, NFA) 1つの入力記号について状態遷移が0個以上 ⇔決定性有限オートマトン (deterministic finite automaton, DFA) 1つの入力記号について状態遷移が1つずつ 前回上げた例はDFA

決定性と非決定性 1対1 q 次の状態へ 入力 a ⇒ある記号列に対して 道がひとつ決まる =決定性 (deterministic) 1対n 道が複数あって 決まらない =非決定性 (nondeterministic) q 次の状態へ

NFAの例 (p.26 図2.5) 1 1 このへん q0 q3 q4 1 1 q2 q1 1

NFAでの受理 入力列に対して状態遷移がひとつでもあれば受理 図2.5での受理される入力列の例:01001 q0, q0, q0, q3, q4, q4 q0 q3 q4 注意: 最終状態でとまらなければならないということはない 1 1 q1 q2 1

NFAの取りうる状態 NFAは同時刻に複数の状態を取りうる 1 2 3 4 5 q0 q3 q1 q4

有限制御機としてのNFA DFA NFA 0 1 1 0 0 1 0 1 1 0 0 1 有限 制御部 有限 制御部 とりうる状態が複数に 0 1 1 0 0 1 0 1 1 0 0 1 有限 制御部 有限 制御部 qx qz qx qy とりうる状態が複数に

NFAの定義式 M = (Q, Σ, δ, q0, F) DFAと同じ?→遷移関数δが違う δ:Q×ΣからQのベキ集合( )への関数 Σ:入力アルファベット q0:初期状態 F :最終状態の集合 =Qの部分集合の集合

NFAの遷移関数の例 (p.27 図2.7) 図2.5の遷移関数δ 1 q0 {q0, q3} {q0, q1} q1 {q2} q2 q3 入力 1 q0 {q0, q3} {q0, q1} q1 {q2} q2 q3 {q4} q4 状態

δの拡張 DFAの時と同様にδを拡張 最終的なδ :Qのベキ集合×Σ*からQのベキ集合への関数 δ:Q×ΣからQのベキ集合への関数 要するに、入力記号だったのを入力列に拡張 最終的なδ :Qのベキ集合×Σ*からQのベキ集合への関数 ここで、PはQの任意の部分集合

受理集合 受理集合L(M)を以下のように定義 L(M)={w|δ(q0, w)がFの状態を少なくとも一つ含む} ここで、M=NFA(Q, Σ, δ, q0, F)とする

ミニテストとレポート ミニテスト 演習問題 2.4 教科書・資料を見ても良い ミニテストとレポートを提出すること 出したら帰って良し