chap1.txt

  
  1 Introduction
  
  In  many situations an automaton is conveniently described through a diagram
  like the following
  
  This  diagram  describes  a  (deterministic)  automaton  with  3 states (the
  elements  of  the  set {1,2,3}). The arrow pointing to the state 1 indicates
  that 1 is the initial state and the two circles around state 3 indicate that
  3  is  a  final  or  accepting  state.  The set {a,b} is the alphabet of the
  automaton;  its  elements are called letters and are the labels of the edges
  of  the  diagram.  The  words  a  ,  ab^2  ,  b^5a^3b  are examples of words
  recognized  by the automaton since they are labels of paths from the initial
  to the final state.
  
  The  set  of  words recognized by an automaton is called the language of the
  automaton.  It  is  a  rational  language  and  may be represented through a
  rational expression. For instance,
  
    Example  
    (aUb)(a(aUb)Ub(aUb))*
  
  
  is a rational expression representing the language of the above automaton.
  
  Kleene's Theorem states that a language is rational if and only if it is the
  language  of  a finite automaton. Both directions of Kleene's Theorem can be
  proved  constructively,  and  these algorithms, to go from an automaton to a
  rational expression and vice-versa, are implemented in this package.
  
  Of course, one has to pay attention to the size of the output produced. When
  producing   a   deterministic  automaton  equivalent  to  a  given  rational
  expression  one can obtain an optimal solution (the minimal automaton) using
  standard algorithms [AHU74].
  
  When  producing  a rational expression for the language of an automaton, and
  taking  into  account  some  reasonable  measure  for the size of a rational
  expression,  to  determine  a  minimal  one  is  apparently  computationally
  difficult.  We  use  here some heuristic methods (to be published elsewhere)
  which in practice lead to very reasonable results.
  
  The  development  of  this  work  has  benefited from the existence of AMoRE
  [MMPTV95],  a  package  written in C to handle Automata, Monoids and Regular
  Expressions.  In  fact,  its  manual  has  been  very useful and some of the
  algorithms implemented here are those implemented in AMoRE. In this package,
  unlike  what  happened  with AMoRE, we do not have to worry about the monoid
  part  in  order  to make it useful to semigroup theorists, since monoids are
  already  implemented  in GAP and we may take advantage of this fact. We just
  need a function to compute the transition semigroup of an automaton.
  
  The  parts  of this package that have not so directly to do with automata or
  rational  expressions  are  put  into  appendices in this manual. Some words
  about these appendices follow.
  
  Using  the  external program Graphviz [DEGKNW02] to graph visualization, one
  can  visualize  automata.  This  very convenient tool presently works easily
  under LINUX.
  
  Given  a  finitely  generated  subgroup  of the free group it is possible to
  compute  a  flower automaton and perform Stallings foldings over it in order
  to obtain an inverse automaton corresponding to the given subgroup.