--- a/paper/c4.tex	Thu Feb 18 22:22:58 2016 +0900
+++ b/paper/c4.tex	Fri Feb 19 01:16:37 2016 +0900
@@ -557,9 +557,74 @@
 \item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。
 \end{itemize}
 
+\begin{lstlisting}[frame=lrbt,label=src:generateTransition,caption=正規表現木の状態割当,numbers=left]
+typedef struct tgValue {
+    StatePtr asterisk;   // last * state of the expression
+    StatePtr startState; // startState of the expression
+    StatePtr endState;
+    TransitionGeneratorPtr tg;
+} TGValue, *TGValuePtr;
+
+TGValue generateTransition(NodePtr n,TGValue tgv, int pass) {
+    if (n->tokenType == '+') {
+        TGValue tgvLeft = tgv;
+        tgvLeft.endState = n->right->state;
+        tgvLeft.asterisk = NULL;
+        tgvLeft = generateTransition(n->left,tgvLeft,pass);
+        TGValue tgvRight = tgv;
+        if (tgvLeft.asterisk) {
+            n->right->state = tgv.endState;
+            tgvRight.startState = tgvLeft.asterisk;
+            tgvRight = generateTransition(n->right,tgvRight,pass);
+            tgvLeft.asterisk = tgvRight.asterisk;
+            return tgvLeft;
+        }
+        tgvRight.asterisk = NULL;
+        if (pass==1) {
+            n->right->state = tgvRight.startState = createState(tgvRight,n->right);
+        } else {
+            tgvRight.startState = n->right->state;
+            tgvRight.tg->stateArray[tgvRight.startState->bitState.bitContainer] = tgvRight.startState ;
+        }
+        tgvRight = generateTransition(n->right,tgvRight,pass);
+        if (tgv.endState && tgvRight.asterisk) tgvRight.startState->accept = tgv.endState->accept;
+        tgvLeft.asterisk = tgvRight.asterisk;
+        return tgvLeft;
+    } else if (n->tokenType == '|') {
+        TGValue tgv1  = generateTransition(n->left,tgv,pass);
+        tgv1.endState = tgv.endState;
+        TGValue tgv2 = generateTransition(n->right,tgv1,pass);
+        return tgv2;
+    } else if (n->tokenType == '*') {
+        TGValue tgvAstah = tgv;
+        tgvAstah.endState = tgvAstah.startState;
+        if (pass==2) tgvAstah.endState->accept = tgv.endState->accept;
+        tgvAstah = generateTransition(n->left,tgvAstah,pass);
+        tgvAstah.asterisk = tgvAstah.startState;
+        return tgvAstah;
+    } else if (n->tokenType == 'c' || n->tokenType == 'a'){
+        TGValue tgv1 = tgv;
+        if (pass==1) {
+            n->stateNum = tgv.startState->stateNum;
+            n->state = tgv.startState;
+        } else {
+            int nextState = tgv.endState->stateNum;
+            n->nextStateNum = nextState;
+            n->nextState = tgv.endState;
+            BitVector bi = createBitVector(nextState);
+            if (n->nextState->accept) bi = bitSet(bi,1);
+            setState(n->cc,bi);
+            tgv1.startState->cc = mergeTransition(tgv1.startState,n->cc);
+        }
+        return tgv1;
+    } else {
+        return tgv;
+    }
+}
+\end{lstlisting}
 ノードに状態を割り振りながら次の状態の遷移先を設定することによって、オートマトンによる状態遷移を表現することができる。
 
-([a-zA-Z]|ab*)*aa
+([a-zA-Z]\textbar ab*)*aa
 
 \begin{figure}[htpb]
   \begin{center}
@@ -747,8 +812,6 @@
 }
 \end{lstlisting}
 
-\newpage
-
 \begin{lstlisting}[frame=lrbt,label=src:task,caption=ceriumGrep のマッチング部分,numbers=left]
 TSValue blockSearch(TSValue tsv,Buffer buff,int task_spawned) {
     tsv.current = tsv.tg->stateStart->tState;

Binary file paper/master_paper.pdf has changed