Neste artigo vamos ver como programar um autómato em C.

Quero contudo verificar se uma palavra (string) introduzida pelo utilizador cumpre certos requisitos.

Vamos dar o exemplo da composição da data:
22-04-2001


Uma data contém primeiramente dois dígitos, um hífen, mais dois dígitos, outro hífen e finalmente quatro dígitos neste formato que é desejado para o exemplo.

(Referir que não vamos dar importância ao conjunto de números por exemplo nos meses, visto que no calendário só existem meses de 1-12, nos vamos alargar o nosso leque de aceitação, portanto aceitamos todos os numero, terão de ser é dois.)


Muito bem, então como vamos fazer isto?

É muito fácil, os passos para a elaboração de um problema deste género tem a seguinte composição:

 

  • Desenhar o nosso autómato
  • Fazer a representação da tabela de transição de estados
  • Computacionar o autómato
Ora vamos então pôr as mãos-à-obra.
 
Pensando assim por alto, sei então que só vou aceitar a “string” introduzida pelo utilizador se ela for:

digitodigitohífendigitodigitohífendigitodigitodigitodigito

99-99-2221
 
 
(Quase poderíamos fazer uma adaptação a matriculas, nada de complicado, mas para já é importante sincronizar os conceitos, visto que resolvendo um exercício resolvemos outro qualquer.)
 
Porreiro, já sabe como vai ser o nosso autómato, agora só falta fazer o seu esquema.
 
Vamos então fazer a sequência normal, ou aquela que ele deve seguir para ser aceite (é sempre assim, fazemos a sequência normal, aquele caminho que tem de percorrer para ser aceite, tratando depois os casos especiais, erros, etc.).
 
Um possível autómato e muito simplificado para que se perceba é o seguinte:
 
 
Aqui temos o autómato, o qual vou descrever estado a estado.
 
Temos q0, que diz respeito ao estado inicial.
  •  Q0 -> se dígito vai para q1 senão vai para q11 o estado de erro
  •  Q1 -> se dígito vai para q2 senão vai para q11 o estado de erro
  •  Q2 -> se for hífen vai para q3 senão para q11 o estado de erro
E assim sucessivamente, caso o autómato termine em q10 então foi aceite senão é rejeitado.
 
Porreiro, já temos o “GRANDE” trabalho feito, agora para que possamos “passar” o autómato para o computador e programa-lo vamos fazer uma tabela de transições, para identificarmos a saída de cada estado. Frisar que é um passo crucial, visto que a tabela irá dar vida a uma matriz no programa.
 
Como construímos então a tabela?
Tabela de Transições (identifica as possíveis saídas de cada estado).
 
Pronto, tendo isto basta só computacionar o autómato, vamos a isso, à ultima fase.
 
Quais os passos a implementar?
  •  Pedir ao utilizador uma string (a string de analise)
  •  Declarar uma variável (estado actual) para percorrer o autómato
  •  Basicamente o nosso autómato vai ser definido por uma matriz, muito parecido com a tabela a cima.
 
Mas como vamos obter esse estado?
 
Muito simples, vamos pedir ao utilizar para inserir uma string, e valida-la.
 
:> 12-12-2002
 
Temos uma função que recebe como parâmetros a nossa matriz, que é o nosso autómato, e passamos também como parâmetro o “estado actual” e o elemento a analisar (neste caso o 1, ou o 2, ou o – depende onde já vamos.)
 
Em seguida nessa função se estamos imaginamos no estado 2, então sabemos que esta string só é aceite se o elemento passado como parâmetro for um hífen.
 
Verificamos e retornamos o novo estado, como se fosse uma máquina de estados, onde entra qualquer coisa e sai qualquer coisa, simples não? Vamos dar uma olhadela no código.
Neste caso entra um estado (diz sempre respeito à linha da matriz, e vamos ver a saída possivel para o caracter (ch)).
 
Neste caso percorremos todos os caracteres da string, e vamos andando no autómato. 
Inicialmente o estado=0, logo vamos a 1º linha da matriz, se entrar um número entra estado=1, então 1->q1 e parece que está a correr bem.
 

 

Última parte do nosso programa é verificar que o estado, é realmente o estado final do autómato, em caso afirmativo temos uma string que é valida.

 

 

 

 

 

 

Como se pode observar algo muito simples, nada de complicado. 
 
Deixo então o código completo do autómato data e também da sua alteração para que na data aceite meses entre 1 e 12.
Código data:
  1. /*###################################
  2. #      CODE BY Pedro Tavares        #
  3. #                                   #
  4. ####################################*/
  5. #include <stdio.h>
  6. //função que permite obter o estado do automato
  7. int delta(int M[12][2],int estado, char ch){
  8.                 //se o estado entrar como -1 sabemos que já não é valido
  9.                 if(estado==-1)
  10.                         return(1);
  11.             //verificar se o caracter que entra é um digito
  12.                 if(ch>=‘0’ && ch<=‘9’)
  13.             return(M[estado][0]);
  14.             //verificar se é um hifen
  15.                 if(ch==‘-‘)
  16.                         return(M[estado][1]);
  17.         if(estado==-1)
  18.                         return(1);
  19.                 else
  20.                         return 1;
  21. }
  22. int main(){
  23.         //declaracao da matriz com todos os estados
  24.         int M[12][2]={
  25.                 {1,11},
  26.                 {2,11},
  27.                 {11,3},
  28.                 {4,11},
  29.                 {5,11},
  30.                 {11,6},
  31.                 {7,11},
  32.                 {8,11},
  33.                 {9,11},
  34.                 {10,11},
  35.                 {11,11},
  36.                 {11,11}
  37.              };
  38.         char buff[15];
  39.         int i,estado=0;
  40.         printf(“Intruduza a data..n);
  41.         gets(buff);
  42.     //percorrer todos os caracteres da string
  43.         for(i=0;i<strlen(buff);i++)
  44.         estado=delta(M,estado,buff[i]);
  45.     //verificar se foi aceite ou nao
  46.         if(estado==10)
  47.                 printf(“data correctan);
  48.         else if(estado==-1)
  49.                 printf(“data incorrectan);
  50.         else
  51.                 printf(“data incorrectan);
  52.         return(0);
  53. }
 
Código data com verificação de meses:
  1. /*###################################
  2. #      CODE BY Pedro Tavares        #
  3. #                                   #
  4. ####################################*/
  5. #include <stdio.h>
  6. #include <string.h>
  7. int delta(int M[12][2],int estado, char ch){
  8.         int i=0;
  9.                 if(estado==-1)
  10.                         return(1);
  11.                 if(ch>=‘0’ && ch<=‘9’){
  12.                         return(M[estado][0]);
  13.                 }
  14.                 if(ch==‘-‘){
  15.                         return(M[estado][1]);
  16.                 }
  17.                 if(estado==-1)
  18.                         return(1);
  19.                 else
  20.                         return 1;
  21. }
  22. int main(){
  23.         int M[12][2]={
  24.                 {1,11},
  25.                 {2,11},
  26.                 {11,3},
  27.                 {4,11},
  28.                 {5,11},
  29.                 {11,6},
  30.                 {7,11},
  31.                 {8,11},
  32.                 {9,11},
  33.                 {10,11},
  34.                 {11,11},
  35.                 {11,11}
  36.              };
  37.         char buff[15];
  38.         int i,estado=0;
  39.         printf(“Intruduza a data..n);
  40.         scanf(“%s”,buff);
  41.         for(i=0;i<strlen(buff);i++){
  42.                 if(estado==-1)
  43.                         break;
  44.                 switch(estado){
  45.                         case 0:
  46.                                 if(atoi(&buff[i])<0 || atoi(&buff[i])>31)
  47.                                         estado=-1;
  48.                         break;
  49.                         case 3:
  50.                                 if(atoi(&buff[i])<0 || atoi(&buff[i])>12)
  51.                                         estado=-1;
  52.                         break;
  53.                 }
  54.                 estado=delta(M,estado,buff[i]);
  55.         }
  56.         if(estado==10)
  57.                 printf(“data correctan);
  58.         else if(estado==-1)
  59.                 printf(“data incorrectan);
  60.         else
  61.                 printf(“data incorrectan);
  62.         return(0);
  63. }