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. }

Pedro Tavares

Pedro Tavares is a professional in the field of information security working as an Ethical Hacker/Pentester, Malware Researcher and also a Security Evangelist. He is also a founding member at CSIRT.UBI and Editor-in-Chief of the security computer blog seguranca-informatica.pt. In recent years he has invested in the field of information security, exploring and analyzing a wide range of topics, such as pentesting (Kali Linux), malware, exploitation, hacking, IoT and security in Active Directory networks.  He is also Freelance Writer (Infosec. Resources Institute and Cyber Defense Magazine) and developer of the 0xSI_f33d – a feed that compiles phishing and malware campaigns targeting Portuguese citizens. Read more here.