研究目的

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

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

• 与えられたから正規表現から正規表現の parser tree に変換することはできている。

現在していること

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

• まずは parser tree から 決定性オートマトンへの変換
• parser tree を入力すると、リスト構造で構成された決定性オートマトンを返す
• concatenation は実装した
• '|'、'*' は書いている途中

どのようなリスト構造か

    
typedef struct bitVector {
    int arrayNum;
    unsigned long *bitContainer;
}BitVector,*BitVectorPtr;

typedef struct bitVectorList {
    bitVectorList *self;
    BitVectorPtr bi;
    bitVectorList* initBvl;
    bitVectorList* next[256];
}BitVectorList, *BitVectorListPtr;
    
    

• BitVectorPtr->bitContainer に状態を格納する。
• BitVectorListPtr->next[c] は 'c' という文字が入力されたときの BitVectorListPtr の遷移先(アドレス)を格納している

図解

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

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

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

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

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

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