// Automates : structures de données + parcours déterministe (complet)


// On ne stocke qu'un automate

typedef int etat ; 
#define MAX_TABLE 20
int automate[MAX_TABLE][MAX_TABLE] ; 
int col_max, lgn_max ; 
int term_table[MAX_TABLE] ; 

int terminal(etat q) {
  return term_table[q] ;
}

int existe_t(etat q, char c) {
  return (automate[q][c-'a'] == -1) ;
}

int delta(etat q, char c) {
  return automate[q][c-'a'] ;
}

void completion()
{
  int i,j ;

  for (i=0 ; i<col_max ; i++)
    automate[0][i] = 0 ; 

  for (i=0 ; i<lgn_max ; i++) 
    for (j=0 ; j<col_max ; j++)
      if (automate[i][j] == -1) automate[i][j]=0 ;
}

int reconnaissance(char * m)
{
  int l = strlen(m) ;
  int i ;
  etat q = 1 ; 

  for (i=0 ; i<l ; i++)
    q = delta(q,m[i]) ;
  return terminal(q) ;
}
      
void cree_auto() {

  //     a b c
  // >1  2 / /
  //  2  2 2 3
  // <3  4 / 2
  // <4  / / 4

  int i ;

  automate[0][0] = -1 ;
  automate[0][1] = -1 ;
  automate[0][2] = -1 ;


  automate[1][0] = 2 ;
  automate[1][1] = -1 ;
  automate[1][2] = -1 ;
  automate[2][0] = 2 ;
  automate[2][1] = 2 ;
  automate[2][2] = 3 ;
  automate[3][0] = 4 ;
  automate[3][1] = -1 ;
  automate[3][2] = 2 ;
  automate[4][0] = -1 ;
  automate[4][1] = -1 ;
  automate[4][2] = 4 ;

  col_max = 3 ;
  lgn_max = 5 ;

  for (i=0 ; i<lgn_max ; i++)
    term_table[i] = 0 ;

  term_table[3] = 1 ;
  term_table[4] = 1 ;
}

void aff_auto() {
  int i, j ;

  printf("    ") ;

  for (j=0 ; j<col_max ; j++)
    printf("%c  ", 'a'+j) ; 
  printf("\n") ;

  for (i=0 ; i< lgn_max ; i++) {
    printf("%c%d:",i==1?'>':(terminal(i)?'<':' '),i) ; 
    for (j=0 ; j<col_max ; j++)
      printf("%2d ",automate[i][j]) ; 
    printf("\n") ;
  }

}
  
main() 
{
  cree_auto() ;
  aff_auto() ;
  completion() ;
  aff_auto() ; 

  if (reconnaissance("aaacac")) printf("OK\n") ;
  if (reconnaissance("baca")) printf("OK\n") ; else printf("Echec\n") ;

}