# HG changeset patch
# User Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
# Date 1455715818 -32400
# Node ID ad9d167cb425cc1a1d1822c6ea238209da957845
# Parent  fbdaf0c213fb55ab0ed80268e2495d615f753766
fix

diff -r fbdaf0c213fb -r ad9d167cb425 paper/c4.tex
--- a/paper/c4.tex	Wed Feb 17 22:22:15 2016 +0900
+++ b/paper/c4.tex	Wed Feb 17 22:30:18 2016 +0900
@@ -550,9 +550,7 @@
 \subsection{正規表現木から DFA・NFA の生成}
 
 次に正規表現木から非決定性有限オートマトン(NFA)、決定性有限オートマトン(DFA)を生成する。
-実際には正規表現木を元にオートマトンを構成していく。その際、深さ優先探索にて木を辿っていき、
 メタ文字のノードが現れた時に一定のルールに沿って文字のノードに状態を割り振っていく。
-ノードに状態を割り振りながら次の状態の遷移先を設定することによって、正規表現木からオートマトンによる状態遷移を表現することができる。
 
 \begin{itemize}
 \item 左子ノードが `*' でない `+' は新しい状態を作る
@@ -560,11 +558,13 @@
 \item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。
 \end{itemize}
 
+ノードに状態を割り振りながら次の状態の遷移先を設定することによって、正規表現木からオートマトンによる状態遷移を表現することができる。
+
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.13]{images/regex/allostate.pdf}
   \end{center}
-  \caption{与えられた正規表現をオートマトンに変換し、それに基いて正規表現木に状態を割り振る}
+  \caption{与えられた正規表現木に状態を割り振る}
   \label{fig:allostate}
 \end{figure}
 
@@ -581,6 +581,13 @@
 \end{figure}
 
 
+\subsection{Subset Construction による NFA から DFA の変換}
+
+生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。
+図\ref{fig:nfaex}はある状態にある文字を入力すると遷移先が複数存在する場合である。状態 4 に `b' が入力されると状態 2 か状態 4 に遷移する。
+このように 1 つの入力に対して遷移先が複数存在すると、どの状態に遷移をしたらよいのかわからくなる。
+このようなオートマトンを非決定性オートマトンという。
+
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.20]{images/regex/nfaex.pdf}
@@ -589,17 +596,10 @@
   \label{fig:nfaex}
 \end{figure}
 
-\subsection{Subset Construction による NFA から DFA の変換}
-
-生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。
-図\ref{fig:nfaex}はある状態にある文字を入力すると遷移先が複数存在する場合である。状態 4 に `b' が入力されると状態 2 か状態 4 に遷移する。
-このように 1 つの入力に対して遷移先が複数存在すると、どの状態に遷移をしたらよいのかわからくなる。
-このようなオートマトンを非決定性オートマトンという。
-
 これを解決する方法として Subset Construction を適用する。
 
 ソースコード\ref{src:cc}
-\begin{lstlisting}[frame=lrbt,label=src:cc,caption=文字クラスの構造体,numbers=left]
+\begin{lstlisting}[frame=lrbt,label=src:cc,caption=文字クラス(charClass)の構造体,numbers=left]
 typedef struct utf8Range {
     unsigned long begin;
     unsigned long end;
@@ -699,7 +699,7 @@
 \end{figure}
 % Print の分割部分の話追加 最後
 
-\begin{lstlisting}[frame=lrbt,label=src:cc,caption=ceriumGrep の TMmain,numbers=left]
+\begin{lstlisting}[frame=lrbt,label=src:result,caption=ceriumGrep の TMmain,numbers=left]
 typedef struct result {
     unsigned char *begin;
     unsigned char *end;
@@ -724,7 +724,7 @@
 }
 \end{lstlisting}
 
-\begin{lstlisting}[frame=lrbt,label=src:cc,caption= Task 側の記述,numbers=left]
+\begin{lstlisting}[frame=lrbt,label=src:task,caption= Task 側の記述,numbers=left]
 TSValue blockSearch(TSValue tsv,Buffer buff,int task_spawned) {
     tsv.current = tsv.tg->stateStart->tState;
     tsv.blk->result = NULL;
@@ -762,7 +762,7 @@
 }
 \end{lstlisting}
 
-\begin{lstlisting}[frame=lrbt,label=src:cc,caption=結果の整合性,numbers=left]
+\begin{lstlisting}[frame=lrbt,label=src:print,caption=結果の整合性,numbers=left]
 static
 TSValue stateSkipOnce(TSValue tsv) {
     if (tsv.matchEnd) {