形式言語とオートマトン2013 ー有限オートマトンー 第5日目 Tokyo University of Technology School of Computer Science © 平成25年5月14日 東京工科大学

形式言語とオートマトン(東京工科大学CS学部) 今日のポイント 有限オートマトン（復習・確認） 正規表現 (regular expression) 正規表現とオートマトンの関係 最簡型オートマトンの作り方 （DFA　－＞　min-DFA） 超高速オートマトン？ 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) まずは、復習から 学而時習之 不亦説乎 By Confucius (孔子) 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 言語(文法)とオートマトンの関係 ---------------------------------------------------------------- 言語 (languages)　　 処理装置 (devices) 句構造言語(PSL) ⇔ Turing 機械 文脈依存言語(CSL) ⇔ 線形有界オートマトン 文脈自由言語(CFL) ⇔ プッシュダウンオートマトン 正規言語(RL) ⇔ 有限オートマトン まずは一番単純なここからだ！ 計算モデル，プログラミング言語設計， ゲームプログラミング等にも役立ちます。 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) さて、… 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 有限オートマトンとは（復習） (英) Finite Automaton (FA) 　　　finite automata (pl.) 有限オートマトンとは、 内部状態の個数が有限個であるオートマトンのことか… 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 有限オートマトンとは（その２） 左の画像は，機械式タイプライタ。 状態を持っている。 １つの操作により，状態が順次変わっていく。 これがオートマトンのイメージ。 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) いろいろなFA Finite Automaton Deterministic Finite Automaton (DFA) or Deterministic Finite State Machine Nondeterministic Finite Automaton (NFA) or Nondeterministic Finite State Machine ε-NFA or NFA with ε-moves or NFA-lambda もう見慣れましたよね！ 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 決定性有限オートマトンの定義 DFA M = ( K, Σ, δ, q0, F ) ただし、 K ：　状態の集合( Kは有限集合) Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 δ： K×Σ∋(qi , a ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K ) 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 非決定性有限オートマトンの定義 NFA M = ( K, Σ, δ, q0, F ) ただし、 K ：　状態の集合( Kは有限集合) Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 δ： K×Σ∋(qi, a ) → Q ⊂ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K ) 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 例：非決定性有限オートマトンM2 NFA M2 = ( K, Σ, δ, q0, F ) ただし、 K ：　{ i, f1, f2, 1, 2 } Σ ：　{ a, b } δ ：　状態遷移関数 （次の頁参照） q0 ：　i F ：　{ f1, f2 } 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 状態遷移関数δ 状態 入力a 入力b i i, 2 i, 1 1 ー f1 2 f2 － 非決定性 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) M2の状態遷移図 i 1 2 a, b ｆ1 ｆ2 b a 状態 入力a 入力b i i, 2 i, 1 1 ー f1 2 f2 － 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) NFA M3の状態遷移図 a, b b i 2 ｆ2 a a ε ε遷移（非決定性の要因） 1 a, b b ｆ1 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 問題 FDA M3 により受理される文字列は次のうちのどれか？ aaaaa aabb abbabb bababaa 形式言語とオートマトン(東京工科大学CS学部)

もう一度ε-NFAの定義から勉強しなおしましょう 問題 FDA　M3 により受理される文字列を５つ以上作ってみなさい。 この問題ができなかった人は、 もう一度ε-NFAの定義から勉強しなおしましょう 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) ここまでは定義の復習 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 新しい話に入りましょう！ 正規表現 (regular expressions) 正規表現は文字列の集合を表すのに便利！ CSにとっては常識です。 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) これからの話の流れ 正規表現 ー＞ NFA NFA ー＞ DFA DFA ー＞ 状態数最小DFA 　（例で詳しく練習しますので、 しっかり付いて来てください。） 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) それでは正規表現の定義から 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) ウォーミングアップ 正規表現は、文字列の集合を表現・記述する。 つまり、正規表現は１つの言語を記述する。 例えば、正規表現 a|b は　文字列 a と b の２つを意味する。 この場合は、正規表現 a|b = { a, b }　といった具合。 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 落ち着いて 読んでください 正規表現の例 文字 a だけからなる言語 { a } は 正規表現では a と書く。 文字列 abc だけからなる言語 { abc } は 正規表現で abc と書く。 言語 { aaa } は正規表現で aaa または a3 と書く。 言語 { a, b } は正規表現で a|b または a+b と書く。 ここまではいいですか？ 形式言語とオートマトン(東京工科大学CS学部)

正規表現の例（２） 言語 { a, aa, aaa, aaaa, aaaaa, …. } は 正規表現で a† と書く。（“a ダガー”と読む） 空文字列は正規表現の１つで、εと書く。 （“エプシロン”と読む） 言語 { ε, b, bb, bbb, bbbb, …} は正規表現で b* と書く。 （“b アスタリスク”とか“b スター”とか”b星印”などと読む） (参考) dagger, asterisk , epsilon 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) チャレンジ問題 それでは、正規表現 a|b* が表しているのはつぎのどれですか？ { a, b } { a, aa, aaa, ・・・, b, bb, bbb, ・・・ } { ε, a, b, bb, bbb, ・・・ } { ε ab, abab, ababab, ・・・ } 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) ここからが今日の本題です！ （試験に必ず出ます。） 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 正規表現をFAで表現してみよう （注）このようなことができることは、 　　　数学的に証明されています。 　　　任意の正規表現に対して、それが表す 　　　言語Lをちょうど受理するFAが存在する。　 　　　また、この逆も成り立つ。 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 正規表現とFAとの対応（その１） R=ε ε i ｆ1 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 正規表現とFAとの対応（その２） 2.R=a a i ｆ1 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 正規表現とFAとの対応（その３） 3.R｜S R i ｆ1 S 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 正規表現とFAとの対応（その４） 4.RS i ｆ1 R S 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 正規表現とFAとの対応（その５） 5.R* ε ε ｆ1 i ε R ε 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 練習 正規表現 a 正規表現 b 正規表現 a|b 正規表現 (a|b)* 正規表現 a(a|b)*bb 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 練習 多少の修業が 必要です。 次の正規表現αをFAで表現しなさい。 α＝ a(a|b)*bb 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) レポート課題No.１ 課題　正規表現 α = 0(0|1)*11 を考える。 正規表現αを非決定性有限オートマトンで 書き表せ。 上記で得られた非決定性有限オートマトンと等価な決定性有限オートントンを作れ。 提出方法：　A4レポート用紙（表紙を付けること） 提出日：平成２５年５月２１日（火）この授業時間開始時 なお，レポートは答えのみではなく，説明も十分階加えること。図表も積極的に使用すると良いですよ。 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 今日はここまで。お疲れ様。 次回は今回までの復習です。正規表現からNFAを求め，それをDFAに変換し，さらにはその簡型DFAを求めます。余力があったら予習しておいてください。 形式言語とオートマトン(東京工科大学CS学部)

形式言語とオートマトン(東京工科大学CS学部) 今日のポイント(再掲) 復習 有限オートマトン 正規表現 (regular expression) 正規表現とオートマトンの関係 NFAからDFAを作る作り方 （NFA　→　DFA） レポート課題説明 （締め切りは次週） オートマトンのイメージ 形式言語とオートマトン(東京工科大学CS学部)