# HG changeset patch # User Masataka Kohagura # Date 1448085429 -32400 # Node ID 0d280684e31f524f9fc3ece9584b6c617e4e84b2 # Parent f9293af3d474eb532c9e1952707f77a83ec2e083 add some files diff -r f9293af3d474 -r 0d280684e31f 2015/1117.html --- 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 @@
- Masataka Kohagura 4th, August , 2015 + Masataka Kohagura 17th, November , 2015
@@ -114,16 +114,20 @@ 正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。
この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。
コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。
- 本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC に対応するライブラリを作成する。 + 本研究では正規表現の問題を並列処理で実装し、速く処理できるようにする。
+

これまで実装しているところ

+

現在していること

正規表現の parser tree から subset constraction に変換するプログラムを書いている途中

@@ -194,6 +198,31 @@
+
+

図解

+

正規表現の parser tree を決定性オートマトンに変換する

+

例) 正規表現 "(a|b)c"

+ +

この決定性オートマトンをリスト構造で表現し出力する

+ +
+ +
+

'|' が含まれた parser tree をうまく決定性オートマトンに変換できていない問題

+

例) 正規表現 "(a|b)c"

+ +

状態 0100 から 0001 に遷移先がなくなっている

+ +
+