■

前回のコーディングでntransというNFA用のデータ構築まで出来、次はnnodeという状態番号を元にしたデータを作成し、その後DFAを構築する。

まず、NFAのntransからnnodeへの変換を考える。
struct Nnode {
  char ch;
  int to;
  Nnode* next;
} *nnode[MAX];
nnodeの添え字はNFAの状態番号とし(ntransのfrom)以下のアルゴリズムで変換する
while(ntransを全てチェック) {
  if (nnode[from]が既に存在する)
    Nnodeを新しく作成し、nnode[from]のnext(リンクリスト)の先頭に追加する。
  else
    nnode[from]を新しく作成する。
}

NFAからDFAへの変換は部分集合構成法とする。
すなわち、ある状態番号xからある文字chで遷移する状態番号の集合をS''とし、さらにその状態からEMPTYで遷移可能な状態番号を加えた集合をS'とする。これを状態番号xが属している集合について全て行い、それらの和集合をSとした時、そのSをDFA上の状態要素とする。
また、NFAの初期状態はそれ自身をただ一つの要素として持つ集合とする。

struct Dtrans {
  int to;  // nnodeの状態番号
  Dtrans* nextTo;  //この添え字のDFAが遷移可能なNFAの状態番号をListで連結しておく
} *dtrans[DFA_MAX]; //添え字はdnodeの添え字と同じでDFAの状態番号
struct Dnode {
  char c;
  Dnode* to; //dnodeのto
} *dnode[DFA_MAX];

状態0のdtransとdnodeを作成する。
while (新しい遷移が得られなくなるまで繰り返す) {
//dnode要検査数>=カレントdnodeチェック番号の間は繰り返す
  while (現在のdnodeから遷移可能なnnodeを全てチェック)
    while (nnodeの連結リストを全てチェック) {
      if (ntrans->ch != EMPTY)
        このdnodeで新しい文字が出た場合、新規状態のdnodeを作成する。 また、その場合は現在のdnodeから連結リストとしてtoの先頭に追加し、dnodeの要検査数をインクリメントする。
　　　　遷移先をdtransに記録する
　    else if (ntrans-> ch == EMPTY)
        遷移先をdtransに記録する
    }
    現在のdnodeの遷移チェック完了
　　カレントのdnodeチェック番号をインクリメントする
  }
}

今一しっくり来てないから実装時に大幅に変えるかも。