astl2.tex

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

\documentclass[10pt]{article}
\usepackage{a4wide,epsf}
\usepackage[latin1]{inputenc}
\usepackage[dvips]{color}
\usepackage{longtable}
%\usepackage{graphics}

% Power set
\newcommand{\pset}[1]{P(#1)}
% Cardinal
\newcommand{\card}[1]{|#1|}
% delta1 and delta2
\newcommand{\dun}{\ensuremath{\delta_{1}} }
\newcommand{\ddeux}{\ensuremath{\delta_{2}} }
% right context
\newcommand{\rcontext}{\ensuremath{\vec{c}}}

\begin{document}
\setlength\arrayrulewidth{0.03cm}
\title{{\bf The Automaton Standard Template Library} \\ {\bf ASTL
        version 2.0} \\ [4ex] Reference Documentation}
\author{Vincent Le Maout}
\maketitle
\newpage
\tableofcontents
\newpage
\section{Introduction}
The Automaton Standard Template Library (ASTL) is a set of generic C++
components for efficient automata manipulation. As any library geared
toward supporting the 
generic programming paradigm, it is made of two distinct parts : a
collection of concepts specific to the automata domain which is
described by 
this documentation and a set of software components (containers,
accessors and algorithms) implementing the concepts. 
\subsection{License}
ASTL is open-source, free software. You can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version. \\

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
check the URL \verb+http://www.fsf.org/+ or read the file
\verb+LICENSE.txt+ containing the GNU Lesser General 
Public License version 2.1. This file can be found at the root
directory of the library.
\subsection{Acknowledgments}
I would like to thank all the people who have worked on and with the
library especially Dominique Revuz for his support and advices on the
code design, Xavier Daragon for writing the very first version of this
documentation and Arnaud Adan for his review and extension to the
weighted automata and transducers. 
\subsection{Availability}
The package and this documentation are downloadable from
\verb+http://astl.sourceforge.net/+ which is the official site for
news, announcements and releases.
\subsection{Supported Compilers}
ASTL 2.0 has been successfully used with GNU g++ 2.96 and later.
% the following compilers :
% \begin{itemize}
% \item GNU g++ 2.96 and later.
% \item Borland C++ 5.5.
% \item Microsoft Visual C++ 6.0 Service Pack 5 with a few minor restrictions.
% \end{itemize}
\subsection{Compiling}
ASTL is made of header files, it does not require to compile
any code prior to using it and therefore requires no specific file to
link to. \\
There is a number of \verb+#defines+ modifying the compiler behavior :
\begin{itemize}
\item \verb+ASTL_USES_NAMESPACE+
\end{itemize}
The only information needed is the \verb+include+ subdirectory
location, for instance: \\
\begin{verbatim}
g++ -I/home/vince/astl/include main.cc
\end{verbatim}
\subsection{Files Hierarchy}
ASTL 2.0 is made of five subdirectories :
\begin{enumerate}
\item \verb+bin+ : command line executables
\item \verb+doc+ : LaTeX documentation source, postcript and PDF
  documentation 
\item \verb+include+ : headers 
\item \verb+src+ : source code for the executables
\item \verb+templates+ : code templates
\item \verb+ext+ : some rather experimental extensions to the library
\end{enumerate}
\section{Definitions and Notations}
\subsection{Finite Automaton}
To make our concepts sufficiently generic to satisfy a broad range of
algorithmic constraints, we add to the classical automaton definition
a set of {\em tags}, that is, any data associated to a state and
needed to apply an algorithm. We will however omit tag-related
considerations whenever they are not relevant. \\

\noindent Let $A(\Sigma, Q, I, F, \Delta, T, \tau)$ be a 7-tuple of finite sets
defined as follows :
\begin{center}
\begin{tabular} {ll}
  $\Sigma$  & An alphabet \\
  $Q$       & A set of states \\
  $I \subseteq Q$ & A set of initial states \\
  $F \subseteq Q$ & A set of final states (also called terminal or
  accepting states) \\
  $\Delta \subseteq (Q \times \Sigma \cup \{ \epsilon \} \times Q)$ &
  A set of transitions \\
  $T$       & A set of tags \\
  $\tau \subset (Q \times T)$ & A set mapping a state to its
  associated tag  \\
\end{tabular} \\ [2ex]
\end{center}
We distinguish one special state noted 0 and called the {\em null} or
{\em sink state}. The {\em label} of a transition $(q, \sigma, p) \in
\Delta$ is
the letter $\sigma$, $q$ is the {\em source} state and $p$ is the {\em
        destination} state or {\em aim}. When $\sigma = \epsilon$ (the empty
word) the transition is said to be an {\em $\epsilon$-transition}. \\
[1ex] 
We call {\em incoming} transitions (respectively {\em outgoing}
transitions) of a state $s$, the set of transitions
$(q, \sigma, p) \in \Delta$ such that $p = s$ (respectively $q =
s$). By default, the transitions of a state are its outgoing
transitions. \\ [1ex] 
We will write $\pset{X}$ for the powerset of a set $X$ and $\card{X}$
for its number of elements. \\ [2ex]
To access $\Delta$ we define two transition functions \dun and \ddeux : \\
  $$\dun \: : \: Q \times \Sigma \cup \{ \epsilon \} \rightarrow \pset{Q} $$ 
  $$\ddeux \: : \: Q \rightarrow \pset{\Sigma \times \pset{Q}} $$ \\
\dun retrieves the set of transitions targets given the source state
and a letter. \ddeux allows to access the set of all the outgoing
transitions of a given state. \\ [1ex]
\dun can be naturally extended to words : \\ 
\begin{center}
\begin{tabular}{rcl}
$ \dun ^{*} \: : Q \times \Sigma^{*}$ & $\rightarrow$ & $\pset{Q} $ \\
$ (q, \epsilon)$ & $\mapsto$ & $q $ \\
$ (q, w \cdot a)$ & $\mapsto$ & $\dun (\dun ^{*}(q,w), a) $ \\
\end{tabular} \\ [3ex]
\end{center}
The {\em right context} of a state $q$ is the set of letters labelling
the outgoing transitions of $q$ : $\rcontext(q) = \{ \sigma \in
\Sigma \mid \exists p \in Q, \: (q, \sigma, p) \in \Delta \}$. \\
A {\em path} is a sequence $c = t_{1} \: t_{2} \: ... \: t_{n}$ of
transitions 
$t_{i} = (q_{i}, \sigma_{i}, p_{i})$ such that $\forall i, t_{i} \in \Delta$ and
for $i < n$, $q_{i+1} = p_{i}$. The path length $n$ is noted $|c|$ and
its label is the concatenation of the transitions letters : $w =
\sigma_{1} \: \sigma_{2} \: ... \: \sigma_{n}$. \\ [1ex]
The language recognized by an automaton $A$ is defined by :
$$ L(A) = \{ w \in \Sigma ^{*} \mid \dun ^{*}(I, w) \cap F \not=
\emptyset \} $$
that is, the labels of the paths leading from an initial state to a
final state. \\

\noindent An automaton is said to be {\em deterministic} iff $I$ is a singleton
and there is at most one transition per state which is labeled by a
given alphabet letter, that is, $\card{\dun(q)} \leq 1$, $\forall q \in
Q$. In this case, \dun is defined as :
$$ \dun(q, \sigma) = \left\{ \begin{array}{ll}
p & \mbox{if $(q, \sigma, p) \in \Delta$} \\
0 & \mbox{otherwise}
\end{array} \right. $$
The sink state acts as failure value for the transition function. \\

\paragraph{Example (figure \ref{fa_example})}
\begin{figure}
\begin{center}
\epsfxsize=6cm
\epsfbox{fa_example.eps}
\caption{Example of NFA}
\label{fa_example}
\end{center}
\end{figure}
$A$ is a non-deterministic automaton with $\Sigma = \{ a, b, c \}$, $Q =
\{ 1,2,3,4,5 \}$, $I = \{ 1 \}$, $F = \{ 2, 5 \}$ and $\Delta = \{
(1,a,2), (2,b,2), (1,b,3), (3,a,5), (1,b,4), (4,c,5) \}$. \\
$L(A) = \{ ab^{*}, ba, bc \}$.
\subsection{Containers \& Cursors}
\section{Getting Started}
This section contains code example ranging from basic automaton
operations to cursors manipulation. They cover all aspect of the
library functionnalities and aim at providing an insight of what can
be done and how\footnote{The code examples make no use of the ASTL
  name space so {\tt ASTL\_USES\_NAMESPACE} should not be defined to
  compile them as is.}. 
\subsection{Declaring a Container}
The automaton containers are class templates parameterized by two
types: the alphabet traits and 
the tag type. By default, the alphabet trait is \verb+plain+ (8 bits
\verb+char+) and the tag type is \verb+empty_tag+ (no tags
needed). Also a predefined alphabet traits called \verb+range+ is
provided. It must be instanciated with a builtin integral type
\verb+T+ followed by two constants \verb+x+ and \verb+y+ of type
\verb+T+ defining a subset
\verb+[x, y]+ of the domain \verb+T+. For example,  
\verb+plain+ is defined as follow : 
\begin{verbatim}
typedef range<char, (char) -128, (char) 127> plain;
\end{verbatim}
\subsubsection{DFA}
ASTL provides eight DFA containers sharing the same
interface. They have homogeneous interfaces and behaviors but
heterogeneous implementations and complexities allowing to choose at
utilization time which one fits best the situation. The following
piece of code declares a variety of containers :
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <string>

int main() 
{
  DFA_map<> A1; 
  DFA_matrix<range<char, 'A', 'Z'> > A2;
  DFA_tr<range<int, 0, 1023> > A3;
  DFA_mtf<french, std::string> A4;
  DFA_hash<std::char_traits<char> > A5;
  DFA_bin<ASCII, int> A6;
}
\end{verbatim}
The declaration of \verb+A1+ uses the template default parameters, it
is equivalent to :
\begin{verbatim}
DFA_map<plain, empty_tag> A1;
\end{verbatim}
\verb+A5+ uses the standard character traits \verb+std::char_traits+
as alphabet traits. It can be used to instanciate all containers
except \verb+DFA_matrix+ and must only be used with builtin types
alphabets. 
\subsubsection{Compact DFA}
A compact automaton is a container adapter parameterized by the
adapted automaton type. It is constructed by copy :
\begin{verbatim}
#include <astl.h>
#include <dfa_mtf.h>
#include <dfa_compact.h>

int main()
{
  DFA_mtf<> A;
  DFA_compact<DFA_mtf<> > C(A);
}
\end{verbatim}
The constructor of \verb+C+ builds a copy of \verb+A+ in a compact
representation.
% \subsubsection{Minimal Dynamic Acyclic DFA}
% The minimal dynamic acyclic automaton is parameterized by two
% allocator types (one for states and one for transitions) which can be
% ommited if no specific allocation scheme is required. It does not
% support tags and the alphabet type is necessarily \verb+char+ :
% \begin{verbatim}
% #include <astl.h>
% #include <dfa_min.h>

% int main()
% {
%   DFA_min<> A; 
% }
% \end{verbatim}
\subsubsection{NFA}
\begin{verbatim}
#include <astl.h>
#include <nfa_mmap.h>

int main()
{
  NFA_mmap<plain, int> A;
}
\end{verbatim}
\subsection{Constructing an Automaton}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <vector>
#include <iterator>

int main()
{
  using namespace std;
  DFA_matrix<> A;
  DFA_matrix<>::state_type q = A.new_state();
  DFA_matrix<>::state_type p = A.new_state();
  A.set_trans(q, 'a', p);
  A.initial(q);
  A.final(p) = true;
  DFA_matrix<>::state_type Q1[10];
  A.new_state(10, Q1);
  vector<DFA_matrix<>::state_type> Q2(10);
  A.new_state(10, Q2.begin());
  vector<DFA_matrix<>::state_type> Q3;
  A.new_state(10, back_inserter(Q3));
}
\end{verbatim}
\subsection{Accessing States Transitions}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <iostream>

int main()
{
  using namespace std;
  typedef DFA_matrix<> DFA;
  DFA A;
  // Construction...
  DFA::state_type q = A.initial();
  DFA::state_type p = A.delta1(q, 'a');
  if (p == A.null_state) cout << "undefined" << endl;
  DFA::edges_type e = A.delta2(q);
  if (e.find('b') == e.end()) cout << "undefined" << endl;
  DFA::edges_type::const_iterator i;
  for(i = e.begin(); i != e.end(); ++i)
    cout << " source " << q 
         << " letter " << i->first 
         << " aim "    << i->second;
}
\end{verbatim}
\subsection{Minimizing Acyclic DFAs}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <minimize.h>

int main()
{
  DFA_matrix<plain, minimization_tag> A;
  // Construction...
  acyclic_minimization(A);
}
\end{verbatim}
\subsection{Matching}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <cursor.h>
#include <language.h>
#include <string>
#include <iostream>

int main()
{
  using namespace std;
  DFA_matrix<> A;
  string w = "word";
  // Construction...
  cursor<DFA_matrix<> > c(A);

  string::const_iterator i = w.begin();
  for(c = A.initial(); i != w.end() && c.forward(*i); ++i);
  if (i == w.end() && c.src_final()) cout << "recognized";

  if (is_in(w.begin(), w.end(), plainc(A))) cout << "recognized too";

  if (is_in(istream_iterator<char>(cin), istream_iterator<char>(),
            plainc(A))) cout << "found on stdin"; 
}
\end{verbatim}
\subsection{Using a Forward Cursor}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <language.h>
#include <cursor.h>
#include <iostream>

int main()
{
  DFA_matrix<> A;
  // Construction...
  forward_cursor<DFA_matrix<> > c(A, A.initial());
  if (c.first_transition()) 
    do 
      std::cout << " source " << c.src() 
                << " letter " << c.letter() 
                << " aim "    << c.aim();
    while (c.next_transition());