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. #   http://infptavares.blogspot.pt  #
  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. }
  23. int main(){
  24.         //declaracao da matriz com todos os estados
  25.         int M[12][2]={
  26.                 {1,11},
  27.                 {2,11},
  28.                 {11,3},
  29.                 {4,11},
  30.                 {5,11},
  31.                 {11,6},
  32.                 {7,11},
  33.                 {8,11},
  34.                 {9,11},
  35.                 {10,11},
  36.                 {11,11},
  37.                 {11,11}
  38.              };        
  39.                
  40.         char buff[15];
  41.         int i,estado=0;
  42.         printf(“Intruduza a data..n);
  43.         gets(buff);
  44.     //percorrer todos os caracteres da string
  45.         for(i=0;i<strlen(buff);i++)
  46.         estado=delta(M,estado,buff[i]);
  47.        
  48.     //verificar se foi aceite ou nao
  49.         if(estado==10)
  50.                 printf(“data correctan);
  51.         else if(estado==-1)
  52.                
  53.                 printf(“data incorrectan);
  54.         else
  55.                 printf(“data incorrectan);
  56.         return(0);
  57. }

Código data com verificação de meses:
  1. /*###################################
  2. #      CODE BY Pedro Tavares        #
  3. #   http://infptavares.blogspot.com #
  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.        
  10.                 if(estado==-1)
  11.                         return(1);
  12.        
  13.                 if(ch>=‘0’ && ch<=‘9’){
  14.                         return(M[estado][0]);
  15.                 }
  16.                 if(ch==‘-‘){
  17.                         return(M[estado][1]);
  18.                 }
  19.        
  20.                 if(estado==-1)
  21.                         return(1);
  22.                 else
  23.                         return 1;
  24.                        
  25. }
  26. int main(){
  27.         int M[12][2]={
  28.                 {1,11},
  29.                 {2,11},
  30.                 {11,3},
  31.                 {4,11},
  32.                 {5,11},
  33.                 {11,6},
  34.                 {7,11},
  35.                 {8,11},
  36.                 {9,11},
  37.                 {10,11},
  38.                 {11,11},
  39.                 {11,11}
  40.              };        
  41.                
  42.         char buff[15];
  43.         int i,estado=0;
  44.         printf(“Intruduza a data..n);
  45.         scanf(“%s”,buff);
  46.         for(i=0;i<strlen(buff);i++){
  47.                 if(estado==-1)
  48.                         break;         
  49.                
  50.                
  51.                
  52.                 switch(estado){
  53.                         case 0:
  54.                                 if(atoi(&buff[i])<0 || atoi(&buff[i])>31)
  55.                                         estado=-1;
  56.                                        
  57.                                        
  58.                         break;
  59.                         case 3:
  60.                                 if(atoi(&buff[i])<0 || atoi(&buff[i])>12)
  61.                                         estado=-1;
  62.                                
  63.                         break;
  64.                 }
  65.                 estado=delta(M,estado,buff[i]);
  66.         }
  67.         if(estado==10)
  68.                 printf(“data correctan);
  69.         else if(estado==-1)
  70.                
  71.                 printf(“data incorrectan);
  72.         else
  73.                 printf(“data incorrectan);
  74.         return(0);
  75. }

Pedro Tavares is a professional in the field of information security, currently working as IT Security Engineer. He is also a founding member and Pentester at CSIRT.UBI and founder 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, hacking, cybersecurity, IoT and security in computer networks.  He is also Freelance Writer.

Read more here.