# HG changeset patch
# User Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
# Date 1281717204 -32400
# Node ID b00e4e5b5368c6f390b9bfadf8c0a761272e4ed1
# Parent  3bf6db862bc7ec1465e6e22bdd25237699517ce7
ver:2

diff -r 3bf6db862bc7 -r b00e4e5b5368 paper.pdf
Binary file paper.pdf has changed
diff -r 3bf6db862bc7 -r b00e4e5b5368 paper.tex
--- a/paper.tex	Fri Aug 13 22:11:43 2010 +0900
+++ b/paper.tex	Sat Aug 14 01:33:24 2010 +0900
@@ -103,19 +103,19 @@
 正規表現は与えられた文字列を受理するかどうかを判定できるパターンマッチン
 グの機構であり, sed, grep, awk を始めとするテキスト処理ツールに広く利用
 されている. 正規表現には定められた文法によって記述され, 例えば,正規表現
-``a*b''は''a''の0回以上の繰り返し直後, ``b'' で終わる文字列(``b'', ``ab'',
-``'aaaab')を受理し, ``a(b\textbar c)'' は ``a''で始まり,直後が ``b'' または
-``c''で終わる文字列(``ab'', ``ac'') を受理する.
+``$a*b$''は''$a$''の0回以上の繰り返し直後, ``$b$'' で終わる文字列(``$b$'' , ``$ab$'',
+``$aaaab$'')を受理し, ``$a(b|c)$'' は ``$a$''で始まり,直後が ``$b$'' または
+``$c$''で終わる文字列(``$ab$'', ``$ac$'') を受理する.
 
 \subsection{正規表現の演算}\label{subsection:regex}
 
 本論文では, 以下に定義された演算をサポートする表現を正規表現として扱う.
 \begin{enumerate}
-\item {連接} 二つの言語LとMの連接(LM)は, Lに族する列を一つとり, そのあとにMに族する列を連
+\item {連接} 二つの言語$L$と$M$の連接($LM$)は, $L$に属する列を一つとり, そのあとに$M$に族する列を連
 接することによってできる列全体から成る集合である.
-\item {集合和} 二つの言語LとM集合和(L\textbar M)は, LまたはM(もしくはその両方)に属する列全体からなる
+\item {集合和} 二つの言語$L$と$M$集合和($L|M$)は, $L$または$M$(もしくはその両方)に属する列全体からなる
 集合である.
-\item {閉包} 言語Lの閉包(L*)とは, Lの中から有限個の列を重複を許して取り出し,
+\item {閉包} 言語$L$の閉包($L*$)とは, $L$の中から有限個の列を重複を許して取り出し,
       それらを連接してできる列全体の集合である.
 \end{enumerate}
 
@@ -134,9 +134,9 @@
 
 ``与えられた正規表現にマッチするテキストを含む''というのは, 行の先頭から
 末尾まで正規表現によるマッチングを行い, 正規表現が受理状態になった時点で
-``含む'' という解釈を行う.つまり, 正規表現 ''(a\textbar s)t'' は, ''at''または''
-st``を受理する正規表現であり, テキスト行''math.``の2~3文字目の''at''に一致す
-るので grep は ``math.'' を出力する. また正規表現''a*''は, ``a''の0回以上の繰
+``含む'' という解釈を行う.つまり, 正規表現 ''$(a|s)t$'' は, ''$at$''または''
+$st$``を受理する正規表現であり, テキスト行''$math.$``の2~3文字目の''$at$''に一致す
+るので grep は ``$math.$'' を出力する. また正規表現''$a*$''は, ``$a$''の0回以上の繰
 り返しを受理する正規表現であり, 空文字も受理するので, grep は全ての行を
 出力することになる.
 
@@ -145,51 +145,72 @@
 下にその変換手方を説明する.
 
 \subsection{正規表現からNFAへの変換}
-NFA は, 入力に対して複数の遷移先持つ状態の集合である.
+NFA({\it Non-deterministic finite-state machine}) は, 入力に対して複数の
+遷移先持つ状態の集合であり, 遷移先が非決定的(Non-deterministic)である.
 
 正規表現が, 等価なNFAに変換できるということを,\ref{subsection:regex}で定義
 した3つの演算について対応するNFAに変換できることから示す.
 
 \begin{enumerate}
 \item {連接} 図\ref{figure:concat}は正規表現 ``AB'' に対応するNFAとなる.
-\item {集合和} 図\ref{figure:union}は正規表現 ``A|B''に対応するNFAとなる.
+\item {集合和} 図\ref{figure:union}は正規表現 ``$A|B$''に対応するNFAとなる.
 \item {閉包} 図\ref{figure:star}は正規表現 ``A*''に対応するNFAとなる.
 \end{enumerate}
 
 \begin{figure}[tH]
 \begin{center}
-\scalebox{0.80}{\includegraphics{fig1.eps}}
+\scalebox{0.60}{\includegraphics{fig1.eps}}
 \end{center}
-\caption{``A''と``B''の連接}
+\caption{``$A$''と``$B$''の連接}
 \label{figure:concat}
 \end{figure}
 
 \begin{figure}[tb]
 \begin{center}
-\scalebox{0.80}{\includegraphics{fig2.eps}}
+\scalebox{0.60}{\includegraphics{fig2.eps}}
 \end{center}
-\caption{``A''と``B''の集合和}
+\caption{``$A$''と``$B$''の集合和}
 \label{figure:union}
 \end{figure}
 
 \begin{figure}[tb]
 \begin{center}
-\scalebox{0.80}{\includegraphics{fig3.eps}}
+\scalebox{0.60}{\includegraphics{fig3.eps}}
 \end{center}
-\caption{``A''の閉包}
+\caption{``$A$''の閉包}
 \label{figure:star}
 \end{figure}
 
 図\ref{figure:union}, \ref{figure:star}において, ラベルのない矢印は無条件
 の遷移を現しており,$\varepsilon$-動作と呼ばれる. また, 二重丸で囲まれた
 状態は受理状態を現しておリ, NFAにおいて入力が終了した時点で,受理状態を保
-持している場合に限り, その文字列を受理したことになる.
+持している場合に限り, その文字列を受理したことになる. なお, NFAは同時に
+複数の遷移先をもつことがあるので, テキストのマッチング途中で複数の状態を
+保持することがある.
 
 現在実装されている正規表現評価器の多くは, 正規表現を内部的にNFAに変換し
 て評価を行っている\cite{R1}. NFAによる実装は, 後述する後方参照や最長一致
-に対応しやすいが, 複数の状態を保持する必要があるため
+に対応しやすいが, 同時に遷移する可能性のある複数の状態を保持する必要があ
+るため, 正規表現の複雑度に多じてマッチングの時間が多くなってしまう場合が
+ある. 文献\cite{R1}では, ``$a?a?a?aaa$'' のような ``$a?^na^n$'' のように
+表現(``$a?$''は''a``か空文字''``を認識する拡張された正規表現お一つ)の評
+価において, NFAベースの正規表現評価器では遷移する状態の数が増えてしまう
+でマッチングにかかる処理時間が$n$の指数的に増加する問題をベンチマーク
+結果と共に指摘している. 文献\cite{K} では正規表現からNFAベースのマッチン
+グ処理を行う IBM 7094 の機械語を生成する例が紹介されている.
 
 \subsection{NFAからDFAへの変換}
+非決定的な遷移を行うNFAから, 決定的な遷移を行うDFA({\it Deterministic
+finite-state machine})に変換する手法を説明する. なお, 遷移が決定的である
+ということは, 1つの入力に対して, 遷移する状態がただ1つであるということを
+指す.
+
+NFAからDFAの変換には, 部分集合構成法(\it{subset construction})と呼ばれる
+方法を利用する. 部分集合構成法では, NFAの ``同時に遷移する可能性のある状
+態の集合''をDFAにおける ``状態''として扱う.
+
+!NFA, DFA の説明をもっと形式的に行います....!
+
 \subsection{DFAから実行バイナリの生成}\label{subsection:compile}
 DFAからの実行バイナリ生成には, 3種類の実装を行った.
 \begin{enumerate}
@@ -200,7 +221,7 @@
 %
 
 \section{評価}
-...
+
 
 \begin{adjustvboxheight} % needed only when Appendix follows
 \begin{thebibliography}{99}