--- a/c4.tex	Wed Feb 10 03:04:40 2016 +0900
+++ b/c4.tex	Wed Feb 10 13:13:58 2016 +0900
@@ -464,6 +464,9 @@
 \subsection{Subset Construction による NFA から DFA の変換}
 Subset Construction は、ある状態から 1 つの入力に対して複数の状態遷移先がある場合、それらの状態 1 つの新しい状態としてまとめ、その新しい状態から新しい遷移先を構成しそれを繰り返す手法である。
 
+図\ref{fig:nfaex}内で入力によって複数の状態に遷移する状態 4 だけに着目する。
+状態 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}
@@ -472,6 +475,9 @@
   \label{fig:nfa}
 \end{figure}
 
+このとき、状態 2 と 4 を組み合わせて一つの状態を新しく作り、その状態に遷移させる。新しく作られる状態の数は状態の組み合わせなので、その状態の組み合わせの和をとっている。
+これより、状態 4 に a か [c-z] を入力すると状態 4 に遷移し、b が入力されると新しい状態 6 に遷移する。
+このような変換をすることによって、入力によって遷移先が一意に決定されるようになる。(図\ref{fig:dfa})
 
 \begin{figure}[htpb]
   \begin{center}
@@ -481,6 +487,9 @@
   \label{fig:dfa}
 \end{figure}
 
+新しい状態が作られたならば、その状態に入力を加えた際の状態遷移も生成する必要がある。
+その状態遷移を生成するには、新しい状態の状態の組み合わせの遷移先を組み合わせることによって遷移先が決定される。\ref{fig:subset}
+
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.2]{images/regex/subset.pdf}

Binary file master_paper.pdf has changed

--- a/memo/result.txt	Wed Feb 10 03:04:40 2016 +0900
+++ b/memo/result.txt	Wed Feb 10 13:13:58 2016 +0900
@@ -1,3 +1,33 @@
+Wed Feb 10 11:06:12 JST 2016
+
+egrep -o '(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)' file/ab500MB.txt >   113.08s user 0.21s system 99% cpu 1:53.29 total
+
+egrep -o '(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)' file/ab500MB.txt > /dev/null  103.32s user 0.18s system 99% cpu 1:43.50 total
+
+egrep -o '(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)' file/ab500MB.txt > /dev/null  98.29s user 0.18s system 99% cpu 1:38.47 total
+15629440
+
+egrep -o '(a|b)*a(a|b)(a|b)(a|b)(a|b)' file/ab500MB.txt > /dev/null  94.72s user 0.18s system 99% cpu 1:34.89 total
+16410912
+
+egrep -o '(a|b)*a(a|b)(a|b)(a|b)' file/ab500MB.txt > /dev/null  90.15s user 0.19s system 99% cpu 1:30.33 total
+line:16410912
+
+egrep -o '(a|b)*a(a|b)(a|b)' file/ab500MB.txt > /dev/null  82.88s user 0.20s system 99% cpu 1:23.09 total
+line:19536800
+
+egrep -o '[A-Z][a-zA-Z0-9_]*' 500MB.txt > /dev/null
+56.34s user 0.16s system 99% cpu 56.506 total
+
+sudo purge 後(キャッシュ消した)
+egrep -o '[A-Z][a-zA-Z0-9_]*' 500MB.txt > /dev/null
+57.37s user 0.22s system 98% cpu 58.382 total
+
+キャッシュがあってもなってもかわらない。
+(ファイルを毎回読み込みながら grep してる?)
+
+-------------------------------------------
+
 Mon Feb  8 17:24:16 JST 2016
 compare cprep egrep ceriumgrep seqsearch
 500MB.txt '[A-Z][a-zA-Z0-9_]*'