chap4.txt

  
  4 User friendly ways to give semigroups and automata
  
  This  chapter  describes two Tcl/Tk graphical interfaces that can be used to
  define and edit semigroups and automata.
  
  
  4.1 Finite automata
  
  4.1-1 XAutomaton
  
  XAutomaton( [A] )  function
  
  The  function    Xautomaton    without arguments opens a new window where an
  automaton  may  be  specified. A finite automaton (which may then be edited)
  may be given as argument.
  
    Example  
    gap> XAutomaton();
          
  
  
  It opens a window like the following:
  
    Var   is the GAP name of the automaton,  States  is the number of states, 
  Alphabet    represents  the  alphabet  and  may  be given through a positive
  integer  (in  this  case  the  alphabet  is understood to be  a,b,c,... ) or
  through a string whose symbols, in order, being the letters of the alphabet.
  The  numbers corresponding to the initial and accepting states are placed in
  the  respective  boxes.  The automaton may be specified to be deterministic,
  non   deterministic  or  with  epsilon  transitions.  After  pressing  the  
  transition  matrix   button the window gets larger and the transition matrix
  of  the  automaton  may  be  given.  The ith row of the matrix describes the
  action of the ith letter on the states. A non deterministic automaton may be
  given as follows:
  
  By  pressing  the  button  Ok  the GAP shell aquires the aspect shown in the
  following  picture and the automaton  ndAUT  may be used to do computations.
  Some  computations  such  as  getting a rational expression representing the
  language of the automaton, the (complete) minimal automaton representing the
  same  language  or  the  transition  semigroup of the automaton, may be done
  directly after pressing the  Functions button.
  
  By  pressing  the  button    View    an  image representing the automaton is
  displayed  in  a  new  window.  An automaton with epsilon transitions may be
  given  as  follows  shown  in  the following picture. The last letter of the
  alphabet  is  always considered to be the ϵ. In the images it is represented
  by @.
  
  A  new  window  with  an image representing the automaton may be obtained by
  pressing the button  View .
  
  In the next example it is given an argument to the function XAutomaton.
  
    Example  
    gap> A := RandomAutomaton("det",2,2);
    < deterministic automaton on 2 letters with 2 states >
    gap> XAutomaton(A);
          
  
  
  It opens a window like the following:
  
  
  4.2 Finite semigroups
  
  The  most  common  ways  to  give  a semigroup to are through generators and
  relations,  a  set  of  (partial)  transformations  as generating set and as
  syntactic semigroups of automata or rational languages.
  
  4.2-1 XSemigroup
  
  XSemigroup( [S] )  function
  
  The  function    XSemigroup    without  arguments opens a new window where a
  semigroup  (or  monoid) may be specified. A finite semigroup (which may then
  be edited) may be given as argument.
  
    Example  
    gap> XSemigroup();
          
  
  
  It  opens  a window like the following: where one may choose how to give the
  semigroup.
  
  
  4.2-2 Semigroups given through generators and relations
  
  In  the  window  opened  by  XSemigroup,  by pressing the button Proceed the
  window should enlarge and have the following aspect. (If the window does not
  enlarge automatically, use the mouse to do it.)
  
   GAP variable  is the GAP name of the semigroup. One has then to specify the
  number  of  generators, the number of relations (which does not to be exact)
  and  whether  one  wants  to  produce  a monoid or a semigroup. Pressing the
  Proceed button one gets:
  
  
  4.2-3 Semigroups given by partial transformations
  
  XSemigroup(poi3); would pop up the following window, where everything should
  be clear:
  
  
  4.2-4 Syntatic semigroups
  
  XSemigroup();  would  pop  up  the  following  window, where we would select
  "Syntatic  semigroup",  press  the  Proceed button and then choose either to
  give  a  "Rational  expression"  or  an "Automaton" by pressing one of those
  buttons:  If "Rational expression" is chosen, a new window pops up where the
  expression  can  be specified: After pressing the Ok button, notice that the
  menu  button  Functions  appears  on  the  main  window (lower right corner)
  meaning that GAP already recognizes the given semigroup: