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

diff -r ad9d167cb425 -r f9851cf9718c paper/c4.tex
--- a/paper/c4.tex	Wed Feb 17 22:30:18 2016 +0900
+++ b/paper/c4.tex	Thu Feb 18 01:56:44 2016 +0900
@@ -545,7 +545,6 @@
 \end{figure}
 
 これらのルールに則って正規表現木を構成し、それを元に DFA・NFA を生成していく。
-\newpage
 
 \subsection{正規表現木から DFA・NFA の生成}
 
@@ -554,7 +553,7 @@
 
 \begin{itemize}
 \item 左子ノードが `*' でない `+' は新しい状態を作る
-\item `\textbar'が親ノードの場合、子ノードの最初の状態は同じ状態。
+\item `\textbar'ノードの場合、左右の子ノードの先頭の状態は同じ状態を割り振る。
 \item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。
 \end{itemize}
 
@@ -570,7 +569,7 @@
 
 これにより、正規表現木に状態の割り振りを行ない、入力を行なったら状態が遷移するようにできた。
 現在の状態(current state)と入力(input)によって次の状態(next state)が一意に決まっており、それをテーブル化して正規表現をファイルにかける。(図\ref{fig:dfaregex})
-このように、ある状態にある入力を与えると次の状態の遷移先が一意に決まるオートマトンのとこを決定性オートマトンという。
+このように、ある状態にある入力を与えると次の状態の遷移先が一意に決まるオートマトンのとこを決定性オートマトン(DFA)という。
 
 \begin{figure}[htpb]
   \begin{center}
@@ -580,13 +579,8 @@
   \label{fig:dfaregex}
 \end{figure}
 
-
-\subsection{Subset Construction による NFA から DFA の変換}
-
 生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。
-図\ref{fig:nfaex}はある状態にある文字を入力すると遷移先が複数存在する場合である。状態 4 に `b' が入力されると状態 2 か状態 4 に遷移する。
-このように 1 つの入力に対して遷移先が複数存在すると、どの状態に遷移をしたらよいのかわからくなる。
-このようなオートマトンを非決定性オートマトンという。
+1 つの入力に対して遷移先が複数存在するようなオートマトンを非決定性オートマトン(NFA)という。
 
 \begin{figure}[htpb]
   \begin{center}
@@ -596,9 +590,39 @@
   \label{fig:nfaex}
 \end{figure}
 
-これを解決する方法として Subset Construction を適用する。
+
+1 入力に対して遷移先が複数存在している場合は、文字によって場合分けをする必要がある。
+図\ref{fig:dfaregex} の
+状態 4 は [a-z] が入力されると状態 4 に遷移し、b が入力されると状態 2 に遷移する。このとき、b が入力されると状態 2 か状態 4 のどちらかに遷移することになる。(図\ref{fig:nfa})
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.2]{images/regex/nfa.pdf}
+  \end{center}
+  \caption{b が入力されるとどちらに遷移すればいいのかわからない}
+  \label{fig:nfa}
+\end{figure}
+
+このとき、状態 2 と 4 を組み合わせて一つの状態を新しく作り、その状態に遷移させる。新しく作られる状態の数は状態の組み合わせなので、その状態の組み合わせの和をとっている。
+これより、状態 4 に a か [c-z] を入力すると状態 4 に遷移し、b が入力されると新しい状態 6 に遷移する。
+このような変換をすることによって、入力によって遷移先が一意に決定されるようになる。(図\ref{fig:dfa})
 
-ソースコード\ref{src:cc}
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.2]{images/regex/dfa.pdf}
+  \end{center}
+  \caption{b が入力されたときは新しい状態を作り、新しい状態に遷移させる}
+  \label{fig:dfa}
+\end{figure}
+
+\subsection{Subset Construction による NFA から DFA の変換}
+
+Subset Construction は、ある複数の状態を 1 つの新しい状態としてまとめ、その新しい状態から新しい遷移先を構成しそれを繰り返す手法である。
+
+ソースコード\ref{src:cc}は文字クラスの構造体である。正規表現木の各ノードそれぞれに、この構造体を持っている。
+文字クラスは二分木で構築されており、それぞれの二分木に文字の範囲である Condition を持っている。
+その Condition の範囲内の文字の入力があれば、次の状態 nextState に遷移する。
+
 \begin{lstlisting}[frame=lrbt,label=src:cc,caption=文字クラス(charClass)の構造体,numbers=left]
 typedef struct utf8Range {
     unsigned long begin;
@@ -618,30 +642,6 @@
 } CharClass, *CharClassPtr;
 \end{lstlisting}
 
-Subset Construction は、ある状態から 1 つの入力に対して複数の状態遷移先がある場合、それらの状態 1 つの新しい状態としてまとめ、その新しい状態から新しい遷移先を構成しそれを繰り返す手法である。
-
-状態 4 は [a-z] が入力されると状態 4 に遷移し、b が入力されると状態 2 に遷移する。このとき、b が入力されると状態 2 か状態 4 のどちらかに遷移することになる。(図\ref{fig:nfa})
-
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.2]{images/regex/nfa.pdf}
-  \end{center}
-  \caption{NFA の例}
-  \label{fig:nfa}
-\end{figure}
-
-このとき、状態 2 と 4 を組み合わせて一つの状態を新しく作り、その状態に遷移させる。新しく作られる状態の数は状態の組み合わせなので、その状態の組み合わせの和をとっている。
-これより、状態 4 に a か [c-z] を入力すると状態 4 に遷移し、b が入力されると新しい状態 6 に遷移する。
-このような変換をすることによって、入力によって遷移先が一意に決定されるようになる。(図\ref{fig:dfa})
-
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.2]{images/regex/dfa.pdf}
-  \end{center}
-  \caption{NFA を Subset Construction によって DFA に変換}
-  \label{fig:dfa}
-\end{figure}
-
 \newpage
 
 新しい状態が作られたならば、その状態に入力を加えた際の状態遷移も生成する必要がある。
diff -r ad9d167cb425 -r f9851cf9718c paper/master_paper.pdf
Binary file paper/master_paper.pdf has changed