Mercurial > hg > Members > masakoha > seminar
diff 2015/1117.html @ 38:0d280684e31f
add some files
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sat, 21 Nov 2015 14:57:09 +0900 |
parents | f9293af3d474 |
children |
line wrap: on
line diff
--- a/2015/1117.html Tue Nov 17 18:21:05 2015 +0900 +++ b/2015/1117.html Sat Nov 21 14:57:09 2015 +0900 @@ -102,7 +102,7 @@ </tr> <tr> <td><div align="right"> - <name>Masataka Kohagura 4th, August , 2015</name> + <name>Masataka Kohagura 17th, November , 2015</name> </div></td> </tr> </tr> @@ -114,16 +114,20 @@ 正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。<br> この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。<br> コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。<br> - 本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC に対応するライブラリを作成する。 + 本研究では正規表現の問題を並列処理で実装し、速く処理できるようにする。 </ul> </div> <div id="cover"> + <h1>これまで実装しているところ</h1> + <ul> + <li>与えられたから正規表現から正規表現の parser tree に変換することはできている。</li> + </ul> <h1>現在していること</h1> <p>正規表現の parser tree から subset constraction に変換するプログラムを書いている途中</p> <ul> <li>まずは parser tree から 決定性オートマトンへの変換</li> - <li>プログラム実行時に正規表現を入力すると、決定性オートマトンのリスト構造を返す</li> + <li>parser tree を入力すると、リスト構造で構成された決定性オートマトンを返す</li> <li>concatenation は実装した </li> <li>'|'、'*' は書いている途中</li> </ul> @@ -194,6 +198,31 @@ </ul> </div> + <div id="cover"> + <h1>図解</h1> + <p>正規表現の parser tree を決定性オートマトンに変換する</p> + <p>例) 正規表現 "(a|b)c"</p> + <ul> + <object data="images/vector/automaton.svg" width="20%" type="image/svg+xml"></object><br> + </ul> + <p>この決定性オートマトンをリスト構造で表現し出力する</p> + <ul> + <object data="images/vector/BitVectorList.svg" width="40%" type="image/svg+xml"></object><br> + </ul> + </div> + + <div id="cover"> + <h1>'|' が含まれた parser tree をうまく決定性オートマトンに変換できていない問題</h1> + <p>例) 正規表現 "(a|b)c"</p> + <ul> + <object data="images/vector/automaton.svg" width="20%" type="image/svg+xml"></object><br> + </ul> + <p> 状態 0100 から 0001 に遷移先がなくなっている</p> + <ul> + <object data="images/vector/BitVectorListMiss.svg" width="20%" type="image/svg+xml"></object><br> + </ul> + </div> + <!-- <div id="cover"> <pre>