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. ####################################*/
  6. #include <stdio.h>
  8. //função que permite obter o estado do automato
  9. int delta(int M[12][2],int estado, char ch){
  12.                 //se o estado entrar como -1 sabemos que já não é valido
  13.                 if(estado==-1)
  14.                         return(–1);
  15.             //verificar se o caracter que entra é um digito
  16.                 if(ch>=‘0’ && ch<=‘9’)
  17.             return(M[estado][0]);
  18.             //verificar se é um hifen
  19.                 if(ch==‘-‘)
  20.                         return(M[estado][1]);
  22.         if(estado==-1)
  23.                         return(–1);
  24.                 else
  25.                         return –1;
  28. }
  30. int main(){
  31.         //declaracao da matriz com todos os estados
  32.         int M[12][2]={
  34.                 {1,11},
  35.                 {2,11},
  36.                 {11,3},
  37.                 {4,11},
  38.                 {5,11},
  39.                 {11,6},
  40.                 {7,11},
  41.                 {8,11},
  42.                 {9,11},
  43.                 {10,11},
  44.                 {11,11},
  45.                 {11,11}
  46.              };
  48.         char buff[15];
  49.         int i,estado=0;
  51.         printf(“Intruduza a data..n“);
  52.         gets(buff);
  54.     //percorrer todos os caracteres da string
  55.         for(i=0;i<strlen(buff);i++)
  56.         estado=delta(M,estado,buff[i]);
  59.     //verificar se foi aceite ou nao
  60.         if(estado==10)
  61.                 printf(“data correctan“);
  62.         else if(estado==-1)
  64.                 printf(“data incorrectan“);
  65.         else
  66.                 printf(“data incorrectan“);
  67.         return(0);
  68. }
 
Código data com verificação de meses:
  1. /*###################################
  2. #      CODE BY Pedro Tavares        #
  3. #                                   #
  4. ####################################*/
  7. #include <stdio.h>
  8. #include <string.h>
  10. int delta(int M[12][2],int estado, char ch){
  12.         int i=0;
  14.                 if(estado==-1)
  15.                         return(–1);
  17.                 if(ch>=‘0’ && ch<=‘9’){
  19.                         return(M[estado][0]);
  20.                 }
  23.                 if(ch==‘-‘){
  24.                         return(M[estado][1]);
  25.                 }
  27.                 if(estado==-1)
  28.                         return(–1);
  29.                 else
  30.                         return –1;
  33. }
  35. int main(){
  37.         int M[12][2]={
  39.                 {1,11},
  40.                 {2,11},
  41.                 {11,3},
  42.                 {4,11},
  43.                 {5,11},
  44.                 {11,6},
  45.                 {7,11},
  46.                 {8,11},
  47.                 {9,11},
  48.                 {10,11},
  49.                 {11,11},
  50.                 {11,11}
  51.              };
  53.         char buff[15];
  54.         int i,estado=0;
  56.         printf(“Intruduza a data..n“);
  57.         scanf(“%s”,buff);
  60.         for(i=0;i<strlen(buff);i++){
  62.                 if(estado==-1)
  63.                         break;
  68.                 switch(estado){
  70.                         case 0:
  71.                                 if(atoi(&buff[i])<0 || atoi(&buff[i])>31)
  72.                                         estado=-1;
  75.                         break;
  77.                         case 3:
  78.                                 if(atoi(&buff[i])<0 || atoi(&buff[i])>12)
  79.                                         estado=-1;
  81.                         break;
  82.                 }
  84.                 estado=delta(M,estado,buff[i]);
  86.         }
  89.         if(estado==10)
  90.                 printf(“data correctan“);
  91.         else if(estado==-1)
  93.                 printf(“data incorrectan“);
  94.         else
  95.                 printf(“data incorrectan“);
  96.         return(0);
  97. }

Deixe um comentário

O seu endereço de email não será publicado. Campos obrigatórios marcados com *