Cerium 上での正規表現の実装

Masataka Kohagura 4th, August , 2015

研究目的

正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。
この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。
コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。
本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC に対応するライブラリを作成する。

現在していること

ソース分割

subset constraction と bitVector

したこと

二分木を表示するための関数を作成

正規表現で生成された二分木を表示

    
% ./regexParser -regex "test"

            t
        +
            s
    +
        e
 +
    t

% ./regexParser -regex "a*bc"

        c
    +
        b
 +
    *
        a