形式言語とオートマトン2013 ー有限オートマトンー 第5日目

Presentation on theme: "形式言語とオートマトン2013 ー有限オートマトンー 第5日目"— Presentation transcript:

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

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

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

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

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

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

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

8 形式言語とオートマトン(東京工科大学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学部)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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