Mercurial > hg > Members > masakoha > seminar
diff 2015/0512.html @ 25:ef709768b9cf
add image
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 12 May 2015 19:06:48 +0900 |
parents | 14d14dcb8219 |
children |
line wrap: on
line diff
--- a/2015/0512.html Mon May 11 15:54:07 2015 +0900 +++ b/2015/0512.html Tue May 12 19:06:48 2015 +0900 @@ -102,7 +102,7 @@ </tr> <tr> <td><div align="right"> - <name>Masataka Kohagura 5th, May , 2015</name> + <name>Masataka Kohagura 12th, May , 2015</name> </div></td> </tr> </tr> @@ -126,24 +126,6 @@ </div> <div id="cover"> - <h1>今日の話題</h1> - <ul> - <li> - 正規表現について - </li> - <li> - オートマトンについて - </li> - <li> - 正規表現の基本三演算 - </li> - <li> - 正規表現の他の演算 - </li> - </ul> - </div> - - <div id="cover"> <h1>正規表現について</h1> <ul> <li> @@ -151,10 +133,9 @@ </li> <li> 文章からあるパターン文字列を検索したいときに使用する <br> - (e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed) - </li> - <li> - 正規表現は有限オートマトンで表現できる + (e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed)<br> + . (ピリオド) : 改行コード以外の任意の1文字<br> + * : 直前の文字の 0 回以上の繰返し </li> </ul> </div> @@ -165,6 +146,21 @@ <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> + </ul> </div> @@ -172,14 +168,17 @@ <h1>正規表現の基本三演算</h1> <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> + <ul>(e.g.) S, RS, RRS, RRRS, ...</ul><br> + <object data="images/vector/star.svg" type="image/svg+xml"></object><br> </li> <li> 基本三演算は結合順位が存在する<br> @@ -202,7 +201,7 @@ <ul>(e.g.) S, RS</ul> </li> <li> - <b>「R{1,3}」</b>: 「{}」の直前のパターンが 1 or 3 回出現するパターン<br> + <b>「R{1,3}」</b>: 「{}」の直前のパターンが 1 〜 3 回出現するパターン<br> <ul>(e.g.) R, RR, RRR</ul> </li> <li> @@ -213,6 +212,31 @@ </ul> </div> + <div id="cover"> + <h1>実装について</h1> + まずは基本三演算を実装していく。 + <ul> + <li> + R*(T|S)U をオートマトンで表現してみる + </li> + <object data="images/vector/rtsu-automaton.svg" type="image/svg+xml"></object> + <li> + 状態と入力に対する遷移先、遷移したかどうかフラグで管理する。 + </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> + </div> + <!-- <div id="cover"> <h1>prog</h1>