astl2.tex

一个类似STL的自动机的源代码库

int main()
{
  DFA_map<> S;
  DFA_bin<> D1, D2;

  DFA_bin<>::state_type i = ccopy(D1, dfirstc(S));
  D1.initial(i);

  i = ccopy(D2, clonec(std::cin));  // read from stdin
  D2.initial(i);

  i = ccopy(D3, dfirstc(notc(S)));  // negation
  D3.initial(i);

  DFA_stream out(std::cout);
  ccopy(out, dfirstc(S));  // write to stdout
}
\end{verbatim}
\paragraph{Notes}
\begin{itemize}
\item This algorithm does not care about the initial state, it is up to the
user to manage any operations related to it.
\item This algorithm is not just a duplication procedure, it is the 
only way (along side \verb+clone+ which is a slight variant of
\verb+ccopy+) to apply an algorithm and to get the result of it as an
automaton container. It is also enough to use almost all of the
operations implemented in ASTL.
\end{itemize}
\paragraph{See Also \\}
\verb+clone+
%%%%%%%%%%%%%%%%%%%%%%%%%%%% CLONE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf clone}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <class DFirstCursor, class DFA>
DFA::state_type 
clone(DFA &out, DFirstCursor first, DFirstCursor last = DFirstCursor());
\end{verbatim}
\paragraph{Description \\}
Copies the source automaton defined by the range \verb+[first, last)+
into the destination automaton \verb+out+ by performing a depth-first
traversal during which all transitions are duplicated.
Returns the first state of the iteration (the first duplicated state).
\paragraph{Definition \\}
\verb+ccopy.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+DFirstCursor+ is a model of depth-first cursor.
\item \verb+DFA+ is a model of DFA.
\item \verb+DFirstCursor::char_type+ is convertible to
  \verb+DFA::char_type+. 
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[first, last)+ is a valid range.
\item Either the source automaton is acyclic or \verb+DFirstCursor+ is
  a depth-first cursor with marker.
\end{itemize}
\paragraph{Complexity \\}
Linear: exactly \verb+last - first+ transitions are duplicated.
\paragraph{Example}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <cursor.h>
#include <ccopy.h>
#include <set_operation.h>
#include <stream.h>
#include <iostream>

int main()
{
  DFA_map<> S;
  DFA_bin<> D1, D2;

  DFA_bin<>::state_type i = clone(D1, dfirstc(S));
  D1.initial(i);

  i = clone(D2, clonec(std::cin));  // read from stdin
  D2.initial(i);

  i = clone(D3, dfirst_markc(notc(S)));  // negation is cyclic
  D3.initial(i);

  DFA_stream out(std::cout);
  clone(out, dfirstc(S));  // write to stdout
}
\end{verbatim}
\paragraph{Notes}
\begin{itemize}
\item This algorithm does not care about the initial state, it is up to the
user to manage any operations related to it.
\item This algorithm is not just a duplication procedure, it is the 
only way (along side \verb+ccopy+ which is a slight variant of
\verb+clone+) to apply an algorithm and to get the result of it as an
automaton container. It is also enough to use almost all of the
operations implemented in ASTL.
\end{itemize}
\paragraph{See Also \\}
\verb+ccopy+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DOT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf dot}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename DFirstCursor>
void dot(ostream &out, DFirstCursor x, DFirstCursor y = DFirstCursor());

template <typename DFirstCursor>
void dot(DFA_dot &out, DFirstCursor x, DFirstCursor y = DFirstCursor());
\end{verbatim}
\paragraph{Description \\} 
Output the automaton defined by the range \verb+[x, y)+ to the output
stream \verb+out+ in a representation suitable as input to the command
\verb+dot+ from GraphViz. \\
The second version of \verb+dot+ allows graphical customization
through the \verb+DFA_dot+ object passed as first argument.
\paragraph{Definition \\}
\verb+dot.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+DFirstCursor+ is a model of depth-first cursor.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[x, y)+ is a valid range.
\end{itemize}
\paragraph{Complexity \\}
Linear
\paragraph{Example}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <cursor.h>
#include <dot.h>
#include <iostream>

int main()
{
  DFA_matrix<> A, B;
  dot(std::cout, dfirstc(A));

  DFA_dot out(std::cout);
  out.state_fontsize(18);     // customize display
  dot(out, dfirst_markc(B));  // if B is cyclic
}
\end{verbatim}
\paragraph{Notes \\}
\verb+dot+ is written as a call to the algorithm \verb+clone+.
\paragraph{See Also \\}
\verb+clone+
%%%%%%%%%%%%%%%%%%%%%%%%%%% ACYCLIC MINIMIZATION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf acyclic\_minimization}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename DFA>
void acyclic_minimization(DFA &a);
\end{verbatim}
\paragraph{Description \\}
Minimizes the size of \verb+a+ by removing unuseful states and
transitions. From the languages point of a view, the minimized version
of \verb+a+ is strictly equivalent to the original one.
\paragraph{Definition \\}
\verb+minimize.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+DFA+ is a model of DFA.
\item \verb+DFA::tag_type+ is \verb+minimization_tag+ defined in
  \verb+minimize.h+ 
\item The transitions of \verb+DFA+ are sorted.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+a+ is acyclic.
\end{itemize}
\paragraph{Complexity \\}
$n\log(n)$ where $n$ is \verb+a.trans_count()+.
\paragraph{Example}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <cursor.h>
#include <minimize.h>
#include <language.h>
#include <iostream>
#include <cassert>

int main()
{
  DFA_matrix<plain, minimization_tag> A;
  unsigned long Q = A.state_count(), T = A.trans_count();
  language(std::cout, dfirstc(A));
  acyclic_minimization(A);
  language(std::cout, dfirstc(A));  // should be the same as above
  assert(A.state_count() <= Q && A.trans_count() <= T);
}
\end{verbatim}
\paragraph{Notes}
\begin{itemize}
\item The requirement that \verb+DFA::tag_type+ be
  \verb+minization_tag+ is a minimal assumption. The tag type can be
  {\em anything} provided that it is {\em at least} a \verb+minimization_tag+.
\item The DFA must stores the transitions in sorted containers which
  means that this algorithm can not be used on containers
  \verb+DFA_mtf+, \verb+DFA_hash+ and \verb+DFA_tr+.
\end{itemize}
\paragraph{See Also \\}
\verb+brzozowski+.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%% BRZOZOWSKI %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf brzozowski}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename DFA1, typename DFA2>
void brzozowski(const DFA1 &A, DFA2 &B);
\end{verbatim}
\paragraph{Description \\}
\verb+brzozowski+ performs a minimization of the possibly cyclic DFA
\verb+A+ and copies the result into the DFA \verb+B+. This is a
generic implementation, on acyclic structures the algorithm
\verb+acyclic_minimization+ is much more efficient.
\paragraph{Definition \\}
\verb+minimize.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+DFA1+ and \verb+DFA2+ are models of DFA.
\item \verb+DFA1::char_type+ is convertible to
  \verb+DFA2::char_type+. 
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+B+ must be empty.
\item \verb+A+ must have sorted transitions.
\end{itemize}
\paragraph{Complexity \\}
\paragraph{Example}
\begin{verbatim}
#include <astl.h>
#include <cursor.h>
#include <minimize.h>
#include <dfa.h>
#include <set_operation.h>
#include <cassert>
#include <iostream>

int main()
{
  DFA_map<> A;
  DFA_bin<> B;
  DFA_matrix<> C;
  brzozowski(A, B);
  assert(B.state_count() <= A.state_count() 
         && B.trans_count() <= A.trans_count());
  brzozowski(B, C);
  assert(isomorph(dfirst_markc(B), dfirst_mark(C)));
}
\end{verbatim}
\paragraph{Notes \\}
The \verb+A+ must stores the transitions in sorted containers which
  means that this algorithm can not be used with source containers of
  type \verb+DFA_mtf+, \verb+DFA_hash+ or \verb+DFA_tr+.
\paragraph{See Also \\}
\verb+acyclic_minimization+.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% REVERSE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf reverse}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename DFA, typename NFA>
void reverse(const DFA &A, NFA &B);
\end{verbatim}
\paragraph{Description \\}
\verb+reverse+ computes a non-deterministic automaton \verb+B+
recognizing the mirror-image language of a DFA \verb+A+, that is : 
$$ w = a_{1} a_{2} ...a_{n} \in L(A) \Leftrightarrow w' =
a_{n} a_{n-1} ...a_{1} \in L(B)$$ This algorithm is reused in the
Brzozowski's minimization algorithm. 
\paragraph{Definition \\}
\verb+minimize.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+DFA+ is a model of DFA.
\item \verb+NFA+ is a model of NFA.
\item \verb+DFA::char_type+ is convertible to \verb+NFA::char_type+. 
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+B+ must be empty.
\end{itemize}
\paragraph{Complexity \\}
$n\log(m)$ where $n$ is \verb+A.trans_count()+ and $m$ is
\verb+A.state_count()+. 
\paragraph{Example}
\begin{verbatim}
#include <astl.h>
#include <ccopy.h>
#include <minimize.h>
#include <determinize.h>
#include <dfa.h>
#include <nfa.h>

int main()
{
  DFA_map<> A;
  NFA_mmap<> B;
  DFA_bin<> C;

  reverse(A, B);
  clone(C, dfirstc(forwarddc(B)));  // determinization
}
\end{verbatim}
%%%%%%%%%%%%%%%%%%%%%%%%% MAKE_HASH %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf make\_hash}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename DFA>
void make_hash(DFA& a);
\end{verbatim}
\paragraph{Description \\}
\verb+make_hash+ computes the needed data to turn the DFA \verb+a+
into a hashing 
automaton. A hashing automaton provides a highly efficient way to
implement a bidirectionnal mapping (known as perfect hash function) 
between strings of any character type and the positive integers. Such
an automaton can be used with the algorithms \verb+hash_value+ and
\verb+value_hash+.
\paragraph{Definition \\}
\verb+hash.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+DFA+ is a model of DFA.
\item \verb+DFA::tag_type+ is \verb+hash_tag+ defined in \verb+hash.h+
\item The transitions of \verb+DFA+ are sorted.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+a+ is acyclic.
\end{itemize}
\paragraph{Complexity \\}
$O(m)$ where $m$ is \verb+A.state_count()+.
\paragraph{Example}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <cursor.h>
#include <hash.h>
#include <iostream>
#include <cassert>
#include <string>

int main()
{
  DFA_matrix<plain, hash_tag> A;