Mercurial > hg > Papers > 2016 > masa-master

comparison c4.tex @ 39:73dd8d6a66b9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add some images
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 10 Feb 2016 02:41:40 +0900
parents 49614a7deaaa
children e6ca2c4eedeb
comparison
equal deleted inserted replaced
38:b2e4ac4e08f2 39:73dd8d6a66b9
302 \subsection{正規表現木から DFA・NFA の生成} 302 \subsection{正規表現木から DFA・NFA の生成}
303 303
304 次に正規表現木から非決定性有限オートマトン(NFA)、決定性有限オートマトン(DFA)を生成する。 304 次に正規表現木から非決定性有限オートマトン(NFA)、決定性有限オートマトン(DFA)を生成する。
305 305
306 オートマトンは、入力に対して状態に対応した処理を行ない結果を出力する仮想的な自動機械である。 306 オートマトンは、入力に対して状態に対応した処理を行ない結果を出力する仮想的な自動機械である。
307 正規表現はオートマトンで表現することができるので、状態と入力(ここでは正規表現)が判れば次はどのような状態になるのか示すことができる。 307 正規表現はオートマトンで表現することができるので、状態と入力(ここでは正規表現)が判れば次はどのような状態になるのか決定される。
308 308
309 \begin{figure}[htpb] 309 \begin{figure}[htpb]
310 \begin{center} 310 \begin{center}
311 \includegraphics[scale=0.2]{images/regex/setstate.pdf} 311 \includegraphics[scale=0.2]{images/regex/setstate.pdf}
312 \end{center} 312 \end{center}
433 \item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。 433 \item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。
434 \end{itemize} 434 \end{itemize}
435 435
436 これにより、正規表現木に状態の割り振りを行ない、入力を行なったら状態が遷移するようにできた。 436 これにより、正規表現木に状態の割り振りを行ない、入力を行なったら状態が遷移するようにできた。
437 現在の状態(current state)と入力(input)によって次の状態(next state)が一意に決まっており、それをテーブル化して正規表現をファイルにかける。(図\ref{fig:dfaregex}) 437 現在の状態(current state)と入力(input)によって次の状態(next state)が一意に決まっており、それをテーブル化して正規表現をファイルにかける。(図\ref{fig:dfaregex})
438 このように、ある状態にある入力を与えると次の状態の遷移先が一意に決まるオートマトンのとこを決定性オートマトンという。
438 439
439 \begin{figure}[htpb] 440 \begin{figure}[htpb]
440 \begin{center} 441 \begin{center}
441 \includegraphics[scale=0.2]{images/regex/dfaregex.pdf} 442 \includegraphics[scale=0.2]{images/regex/dfaregex.pdf}
442 \end{center} 443 \end{center}
443 \caption{dfa} 444 \caption{dfa}
444 \label{fig:dfaregex} 445 \label{fig:dfaregex}
445 \end{figure} 446 \end{figure}
446 447
447 しかし、生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。 448 しかし、生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。
448 図\ref{fig:nfaregex} 449 図\ref{fig:nfaex}はある状態にある文字を入力すると遷移先が複数存在する場合である。状態 4 に `b' が入力されると状態 2 か状態 4 に遷移する。
449 450 このように 1 つの入力に対して遷移先が複数存在すると、どの状態に遷移をしたらよいのかわからくなる。
451 このようなオートマトンを非決定性オートマトンという。
452
453 これを解決する方法として Subset Construction を適用する。
454
455 \begin{figure}[htpb]
456 \begin{center}
457 \includegraphics[scale=0.2]{images/regex/nfaex.pdf}
458 \end{center}
459 \caption{1 入力に対して遷移先が複数存在する(NFA)}
460 \label{fig:nfaex}
461 \end{figure}
450 462
451 \subsection{Subset Construction による NFA から DFA の変換} 463 \subsection{Subset Construction による NFA から DFA の変換}
464 Subset Construction は、ある状態から 1 つの入力に対して複数の状態遷移先がある場合、それらの状態 1 つの新しい状態としてまとめ、その新しい状態から新しい遷移先を構成しそれを繰り返す手法である。
465
466 \begin{figure}[htpb]
467 \begin{center}
468 \includegraphics[scale=0.2]{images/regex/nfa.pdf}
469 \end{center}
470 \caption{NFA の例}
471 \label{fig:nfa}
472 \end{figure}
473
474
475 \begin{figure}[htpb]
476 \begin{center}
477 \includegraphics[scale=0.2]{images/regex/dfa.pdf}
478 \end{center}
479 \caption{NFA を Subset Construction によって DFA に変換}
480 \label{fig:dfa}
481 \end{figure}
482
483 \begin{figure}[htpb]
484 \begin{center}
485 \includegraphics[scale=0.2]{images/regex/subset.pdf}
486 \end{center}
487 \caption{Subset Construction によって新しく生成された状態の状態遷移の生成}
488 \label{fig:subset}
489 \end{figure}
490
491 \begin{figure}[htpb]
492 \begin{center}
493 \includegraphics[scale=0.2]{images/regex/subsetauto.pdf}
494 \end{center}
495 \caption{Subset Construction 後のオートマトンの変化}
496 \label{fig:subsetauto}
497 \end{figure}
498
452 on the fly 499 on the fly
453 subset construction で使わない状態は生成しないで済む 500 subset construction で使わない状態は生成しないで済む
454 501
455 \subsection{DFA を元にパターンマッチを行う} 502 \subsection{DFA を元にパターンマッチを行う}
456 503
457 \subsection{(Word をノードに含める話)} 504 \subsection{(Word をノードに含める話)}
458 505
459 IBM stream processing 506 IBM stream processing
460
461 \begin{figure}[htpb]
462 \begin{center}
463 \includegraphics[scale=0.2]{images/regex/dfa.pdf}
464 \end{center}
465 \caption{dfa}
466 \label{fig:dfa}
467 \end{figure}
468
469 \begin{figure}[htpb]
470 \begin{center}
471 \includegraphics[scale=0.2]{images/regex/nfa.pdf}
472 \end{center}
473 \caption{nfa}
474 \label{fig:nfa}
475 \end{figure}
476
477 \begin{figure}[htpb] 507 \begin{figure}[htpb]
478 \begin{center} 508 \begin{center}
479 \includegraphics[scale=0.2]{images/regex/transitiontable.pdf} 509 \includegraphics[scale=0.2]{images/regex/transitiontable.pdf}
480 \end{center} 510 \end{center}
481 \caption{Transition Table} 511 \caption{Transition Table}