Mercurial > hg > Members > masakoha > seminar
diff 2015/0519.html @ 27:33f5506858bd
fix
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 02 Jun 2015 17:08:31 +0900 |
parents | cbdddbccca58 |
children |
line wrap: on
line diff
--- a/2015/0519.html Tue May 19 18:15:44 2015 +0900 +++ b/2015/0519.html Tue Jun 02 17:08:31 2015 +0900 @@ -125,116 +125,64 @@ </ul> </div> - <div id="cover"> - <h1>正規表現について</h1> - <ul> - <li> - 文字列の一部をパターン化して表現する手法 - </li> - <li> - 文章からあるパターン文字列を検索したいときに使用する <br> - (e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed)<br> - . (ピリオド) : 改行コード以外の任意の1文字<br> - * : 直前の文字の 0 回以上の繰返し - </li> - </ul> - </div> <div id="cover"> - <h1>オートマトンについて</h1> + <h1>正規表現を有限オートマトンで書いてみる</h1> + 例題 : (a|aa|aaa)*b <ul> - <li> - 入力に対して内部の状況に応じた処理を行う結果を出力する仮想的な自動機械の概念 - </li> - <li> - 正規表現はオートマトンで表現することができる。 - </li> - <li> - 非決定性有限オートマトン NFA(Non-deterministic Finite Automaton)と、非決定性有限オートマトンDFA(Deterministic Finite Automaton)が存在する。 - </li> - <li> - 非決定性有限オートマトン : 1つの入力に対して複数の遷移先が存在する - </li> - <object data="images/vector/nfa.svg" type="image/svg+xml"></object> - <li> - 決定性有限オートマトン : 1つの入力に対して遷移先が1つだけ - </li> - <object data="images/vector/dfa.svg" type="image/svg+xml"></object> - + <object data="images/vector/automata.svg" type="image/svg+xml"></object><br> + </ul> + もうちょっとスッキリさせる + <ul> + <object data="images/vector/dfa2tosubset.svg" type="image/svg+xml"></object><br> </ul> </div> <div id="cover"> - <h1>正規表現の基本三演算</h1> + <h1>正規表現を有限オートマトンで書いてみる</h1> + 例題 : ab(ab)+ <ul> - <li> - 正規表現は「連接」「選択」「繰返し」の演算が備えられている<br> - R,S という 2 つの正規表現が存在すると仮定する。<br> - <b>連接 「RS」</b>: R の直後に S が続くパターン<br> - <ul>(e.g.) RS, RRS, RSS, RRSS, ...<br></ul> - <object data="images/vector/rensetsu.svg" type="image/svg+xml"></object><br> - <b>選択 「R|S」</b>: R もしくは S が出現するパターン<br> - <ul>(e.g.) R, S, RS, ...<br></ul> - <object data="images/vector/sentaku.svg" type="image/svg+xml"></object><br> - <b>繰返し 「R*S」</b>: 「*」の直前(R)が 0 回以上出現するパターン<br> - <ul>(e.g.) S, RS, RRS, RRRS, ...</ul><br> - <object data="images/vector/star.svg" type="image/svg+xml"></object><br> - </li> - <li> - 基本三演算は結合順位が存在する<br> - <ul>繰返し > 連接 > 選択</ul> - </li> + <object data="images/vector/abab.svg" type="image/svg+xml"></object><br> + </ul> + テキストが abab の途中で分割される場合を考える + <ul> + <object data="images/vector/ababautomata.svg" type="image/svg+xml"></object><br> + </ul> + 分割されたファイルの1コ前の終わりが状態(3)の場合で、分割されたファイルの先頭が b の場合状態(4)に遷移して受理される。(正規表現にマッチする) + <ul> + <object data="images/vector/ababtable.svg" type="image/svg+xml"></object><br> </ul> </div> <div id="cover"> - <h1>正規表現の他の演算</h1> + <h1>正規表現を有限オートマトンで書いてみる</h1> + 例題 : ab(ab)+ <ul> - <li> - <b>「R+S」</b>: 「+」の直前のパターンが 1 回以上出現するパターン<br> - <ul>(e.g.) RS, RRS, RRRS, ...</ul> - <ul>R+S ≡ R(R*)S</ul> - </li> - <li> - <li> - <b>「R?S」</b>: 「?」の直前のパターンが 0 or 1 回出現するパターン<br> - <ul>(e.g.) S, RS</ul> - </li> - <li> - <b>「R{1,3}」</b>: 「{}」の直前のパターンが 1 〜 3 回出現するパターン<br> - <ul>(e.g.) R, RR, RRR</ul> - </li> - <li> - <b>「R{1,}」</b>: 「{}」の直前のパターンが 1 回以上出現するパターン<br> - <ul>(e.g.) R, RR, RRR, ...</ul> - <ul>R+S ≡ R(R*)S ≡ R{1,}S</ul> - </li> + <object data="images/vector/abab.svg" type="image/svg+xml"></object><br> + </ul> + テキストが abab の途中で分割される場合を考える + <ul> + <object data="images/vector/ababautomata.svg" type="image/svg+xml"></object><br> + </ul> + 分割されたファイルの1コ前の終わりが状態(3)の場合で、分割されたファイルの先頭が b の場合状態(4)に遷移して受理される。(正規表現にマッチする) + <ul> + <object data="images/vector/ababtable.svg" type="image/svg+xml"></object><br> </ul> </div> <div id="cover"> - <h1>実装について</h1> - まずは基本三演算を実装していく。 - <ul> + <h1>近況報告</h1> + <ul> <li> - R*(T|S)U をオートマトンで表現してみる - </li> - <object data="images/vector/rtsu-automaton.svg" type="image/svg+xml"></object> - <li> - 状態と入力に対する遷移先、遷移したかどうかフラグで管理する。 + インプレス Think IT より連載の依頼が飛んできました。 </li> - <pre> - <code> -typedef struct Automaton { - int state; - unsigned char input_char; - int next_state; - bool next_state; -}; - </code> -</pre> - <object data="images/vector/rtsu-automatondata.svg" type="image/svg+xml"></object> - </ul> + <li> + 6回ほど連載 + </li> + <li> + Unity 4からUnity 5 への変更点、新機能等の概要と、実際に簡単なゲーム製作記事。 + </li> + </ul> </div> <!--