Ir para conteúdo
KrilMun

Algoritmo AFD

Recommended Posts

Boa noite pessoal,

 

É meu primeiro post no fórum, havia descoberto ele há alguns dias procurando sobre o mesmo assunto do título, e acho que vocês poderiam me ajudar. O seguinte código representa um AFD simples para o reconhecimento de constantes reais com exponenciação.

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int testePalavra(int contador, char palavra[]);
int testePosicao(int e, int estadoFinal[]);

int main() {
    char palavra[] = "+32E-52E";

    int estadoFinal[] = {3, 5, 9};
    int estadoIncial = 0;
    int i;
									//+ //- //. //E //Digito
    int tabelaTransicoes[10][5] =	{{1,  1,  2, -1,  3},  //q0
    								{-1, -1,  2, -1,  3},  //q1
    								{-1, -1, -1, -1,  5},  //q2
    								{-1, -1,  4,  6,  3},  //q3
    								{-1, -1, -1, -1,  5},  //q4
    								{-1, -1, -1,  6,  5},  //q5
    								{ 8,  8, -1, -1,  9},  //q6
    								{-1, -1, -1, -1,  9},  //q8
    								{-1, -1, -1, -1,  9}}; //q9

    int e = estadoIncial;
    printf("Estado Inicial q%d\n", e);

    int contador = 0;
    for (i = 0; i < strlen(palavra); i++) {
        char c = palavra[i];
        int coluna;
        
		if (c == '+') {
        	printf("Caractere lido: %c\n", c);
            coluna = 0;
        } else if (c == '-') {
        	printf("Caractere lido: %c\n", c);
            coluna = 1;
    	} else if (c == '.') {
        	printf("Caractere lido: %c\n", c);
            coluna = 2;
        } else if (c == 'E') {
        	printf("Caractere lido: %c\n", c);
            coluna = 3;
        } else if (isdigit(c)) {
        	printf("Caractere lido: %c\n", c);
            coluna = 4;
        } else {
        	printf("Caractere lido: %c\n", c);
            coluna = -1;
        	printf("   Transicao invalida: Caractere nao aceito!\n");
            break;
        }

        e = tabelaTransicoes[e][coluna];

        if (e != -1) {
            contador++;
            printf("   Transicao para q%d", e);
            if (testePosicao(e, estadoFinal))
            	printf(" | Estado Final");
            else
            	printf(" | Estado Nao-Final");
            printf("\n");
        }
        else{
        	printf("   Transicao invalida: Erro de leitura!\n");
            break;
        }
    }

    if ((testePalavra(contador, palavra)) && (testePosicao(e, estadoFinal))) {
        printf("\nA palavra %s foi aceita pelo AFD!", &palavra);
    } else{
        printf("\nA palavra %s foi recusada pelo AFD!", &palavra);
    }
    
    return 0;
}

int testePalavra(int contador, char palavra[]){ //Teste para verificar se a 
	if (contador == strlen(palavra))
		return 1;
	else
		return 0;
}

int testePosicao(int e, int estadoFinal[]){ //Teste para verificar se a posição em que a palavra terminou é estado final
	int i;
	int status = 0;
	
	for(i = 0; i < sizeof(estadoFinal); i++){
		if (e == estadoFinal[i]){
			status = 1;
			break;
		}
	}
	
	return status;
}
int tabelaTransicoes[10][5] =	{{1,  1,  2, -1,  3},  //q0
    								{-1, -1,  2, -1,  3},  //q1
    								{-1, -1, -1, -1,  5},  //q2
    								{-1, -1,  4,  6,  3},  //q3
    								{-1, -1, -1, -1,  5},  //q4
    								{-1, -1, -1,  6,  5},  //q5
    								{ 8,  8, -1, -1,  9},  //q6
    								{ 0,  0,  0,  0,  0},  //q7
    								{-1, -1, -1, -1,  9},  //q8
    								{-1, -1, -1, -1,  9}}; //q9

//EDIT 2: Problema corrigido apenas por inserir um novo array na matriz, "q7", com todos os valores 0.
//O porquê eu não sei hahahaha ainda estou em dúvida! Se alguém souber responder, agradeço!

#Estou fazendo um trabalho da faculdade, em que foi pedido um AFD para reconhecimento de constantes reais com exponenciação, e acabei de concluí-lo, porém estou #com um erro totalmente sem sentido, que ainda não consegui compreender o que é.

 

#A palavra que estou usando como teste demonstra o erro, segundo a tabela de transições, quando eu chego no estado q9 eu não posso mais sair dele (e isso está explícito #na matriz que eu declarei), porém de alguma forma ela está voltando para q5, o que possibilita inserir um E após os dígitos.


#Preciso da resposta urgente, quem puder me ajudar agradeço!

 

Problema acima corrigido, agora preciso saber o porquê de essa alteração ter resolvido..

Editado por KrilMun
EDIT 2: Resolução do problema.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Eu fiz aqui um teste de mesa com o que você passou no código e ao chegar no primeiro dígito da palavra ele já não aceita (apesar de seguir em frente) porque o novo valor de e corresponde a um dos estados finais. Então a única alteração que fiz no código foi inserir um break no if:

 

 if (testePosicao(e, estadoFinal)) {
       printf(" | Estado Final");
       break;
  }



-> Não esqueça que existe um loop lendo a palavra. Para uma palavra válida o estado final corresponde ao final da palavra (último caractere lido, a princípio... não me parece que você está trabalhando com transições "vazias") então isso vai corresponder ao final do loop (a condição do for vai ser falsa e o loop, interrompido). Mas para uma palavra inválida, cujo estado final pode estar já no início da palavra, esse loop precisa ser interrompido "no braço".

-> Altere aquele sizeof no loop. O sizeof te dá o tamanho do array em *bytes*. Se você precisa do tamanho como quantidade de elementos presentes no array, precisa dividir o tamanho em bytes do array pelo tamanho em bytes do tipo do array (sizeof(estadoFinal)/sizeof(int))

Compartilhar este post


Link para o post
Compartilhar em outros sites
Em 2017-6-21 at 12:40, _Isis_ disse:

->Altere aquele sizeof no loop. O sizeof te dá o tamanho do array em *bytes*. Se você precisa do tamanho como quantidade de elementos presentes no array, precisa dividir o tamanho em bytes do array pelo tamanho em bytes do tipo do array (sizeof(estadoFinal)/sizeof(int))

Agradeço pela explicação! Não sabia deste detalhe, ou talvez não lembrasse, estou meio enferrujado em C hahaha..

 

Em 2017-6-21 at 12:40, _Isis_ disse:

 Então a única alteração que fiz no código foi inserir um break no if

 

-> Não esqueça que existe um loop lendo a palavra. Para uma palavra válida o estado final corresponde ao final da palavra (último caractere lido, a princípio... não me parece que você está trabalhando com transições "vazias") então isso vai corresponder ao final do loop (a condição do for vai ser falsa e o loop, interrompido). Mas para uma palavra inválida, cujo estado final pode estar já no início da palavra, esse loop precisa ser interrompido "no braço".

Agora, um pequeno adendo aqui, segundo o AFD pelo problema proposto, a palavra pode tanto sair de alguns estados finais, quanto retornar a eles, o importante é que o último caractere lido pelo mesmo seja um estado final, portanto poderia chegar a um estado final no meio da palavra e ir para um estado não-final e voltar a assumir um estado final novamente ao fim da palavra.

 

Perceba (pela matriz) que a palavra pode transitar do estado q3 (final) para o estado q6 (não final), e deste para o q9 (final novamente), e ser aceita (válida). Apenas invertendo a ordem do que você escreveu "Para uma palavra válida, o final da palavra corresponde a um estado final".

 

Não sei se você fez a alteração apenas por teste, mas a ideia aqui é justamente não ter um break.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Como que ficou teu autômato no papel? Tava tentando lembrar como era a gramática do C p/ constante com exponenciação, mas não achei o documento técnico.
https://goo.gl/photos/9YdLNgkxCAXfEXdN7

(Faltou a transição do q0 p/ q6 caso você informe qq coisa diferente de +,- ou dígito)
Entenda o asterisco como "qualquer coisa que não tenha uma transição especificada".

Compartilhar este post


Link para o post
Compartilhar em outros sites
1 hora atrás, _Isis_ disse:

Como que ficou teu autômato no papel? Tava tentando lembrar como era a gramática do C p/ constante com exponenciação, mas não achei o documento técnico.
https://goo.gl/photos/9YdLNgkxCAXfEXdN7

(Faltou a transição do q0 p/ q6 caso você informe qq coisa diferente de +,- ou dígito)
Entenda o asterisco como "qualquer coisa que não tenha uma transição especificada".

 

Segue o diagrama de transições do AFD

 

ub_VgH2_QkmcITBx3Bm1eQ.png

Compartilhar este post


Link para o post
Compartilhar em outros sites

Isso te ajuda? Não tentei simplificar o autômato.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
const int ESTADOS_FINAIS[] = {6,8,9};
const int ESTADOS_ERRO[] = {9};
const int AFD[11][6] = { // + , - , . , digito , 'E', *
                        {  1 , 1 , 9 ,   2    ,  9 , 9 }, // q0
                        {  9 , 9 , 9 ,   2    ,  9 , 9 }, // q1
                        {  9 , 9 , 3 ,   2    ,  5 , 9 }, // q2
                        {  9 , 9 , 9 ,   4    ,  9 , 9 }, // q3
                        {  9 , 9 , 9 ,   4    ,  5 , 9 }, // q4
                        { 10 ,10 , 9 ,   6    ,  9 , 9 }, // q5
                        {  9 , 9 , 7 ,   6    ,  9 , 9 }, // q6
                        {  9 , 9 , 9 ,   8    ,  9 , 9 }, // q7
                        {  9 , 9 , 9 ,   8    ,  9 , 9 }, // q8
                        {  9 , 9 , 9 ,   9    ,  9 , 9 }, // q9
                        {  9 , 9 , 9 ,   6    ,  9 , 9 }  // q10
                      };
                    
int indexOf(const int * arr, int size, int element) {
  int i;
  for(i=0; i<size && element != arr[i]; i++);
  return (i >= size)? -1 : i;
}

int isErro(int estado) {
  return (indexOf(ESTADOS_ERRO, sizeof(ESTADOS_ERRO)/sizeof(int), estado) != -1);
}

int isFinal(int estado) {
  return (indexOf(ESTADOS_FINAIS, sizeof(ESTADOS_FINAIS)/sizeof(int), estado) != -1);
}

int localizar_estado(char c, int estado_atual) {
  int proximo_estado = 9; // define o estado de erro como padrão.
  
  if (c == '+') {
    proximo_estado = AFD[estado_atual][0];
  } else if (c == '-') {
    proximo_estado = AFD[estado_atual][1];
  } else if (c == '.') {
    proximo_estado = AFD[estado_atual][2];
  } else if (isdigit(c)) {
    proximo_estado = AFD[estado_atual][3];
  } else if (c == 'e') {
    proximo_estado = AFD[estado_atual][4];
  } else {
    proximo_estado = AFD[estado_atual][5];
  }
  return proximo_estado;
}

int main(void) {
  const char * palavra = "+3.389E-10.8";
  int estado_atual = 0;
  int i;
  
  for(i = 0; i < strlen(palavra) && !isErro(estado_atual); i++) {
    printf("-- Estado atual: %d --\n", estado_atual);
    printf("Processando caractere: %c\n", palavra[i]);
    estado_atual = localizar_estado(tolower(palavra[i]), estado_atual);
  }
  
  if (i >= strlen(palavra) && !isFinal(estado_atual)) {
    printf("Palavra \t%s\t não aceita.", palavra);
  } else {
  
    if (isFinal(estado_atual)) {
      printf("Palavra \t %s \t %saceita.\n", palavra, isErro(estado_atual)? "não ":"");
    } else {
      printf("Palavra \t %s \t não aceita.\n");
    }
    
  }
  return 0;
}

 

Compartilhar este post


Link para o post
Compartilhar em outros sites
37 minutos atrás, _Isis_ disse:

Isso te ajuda? Não tentei simplificar o autômato.


#include <stdio.h>
#include <string.h>
#include <ctype.h>
const int ESTADOS_FINAIS[] = {6,8,9};
const int ESTADOS_ERRO[] = {9};
const int AFD[11][6] = { // + , - , . , digito , 'E', *
                        {  1 , 1 , 9 ,   2    ,  9 , 9 }, // q0
                        {  9 , 9 , 9 ,   2    ,  9 , 9 }, // q1
                        {  9 , 9 , 3 ,   2    ,  5 , 9 }, // q2
                        {  9 , 9 , 9 ,   4    ,  9 , 9 }, // q3
                        {  9 , 9 , 9 ,   4    ,  5 , 9 }, // q4
                        { 10 ,10 , 9 ,   6    ,  9 , 9 }, // q5
                        {  9 , 9 , 7 ,   6    ,  9 , 9 }, // q6
                        {  9 , 9 , 9 ,   8    ,  9 , 9 }, // q7
                        {  9 , 9 , 9 ,   8    ,  9 , 9 }, // q8
                        {  9 , 9 , 9 ,   9    ,  9 , 9 }, // q9
                        {  9 , 9 , 9 ,   6    ,  9 , 9 }  // q10
                      };
                    
int indexOf(const int * arr, int size, int element) {
  int i;
  for(i=0; i<size && element != arr[i]; i++);
  return (i >= size)? -1 : i;
}

int isErro(int estado) {
  return (indexOf(ESTADOS_ERRO, sizeof(ESTADOS_ERRO)/sizeof(int), estado) != -1);
}

int isFinal(int estado) {
  return (indexOf(ESTADOS_FINAIS, sizeof(ESTADOS_FINAIS)/sizeof(int), estado) != -1);
}

int localizar_estado(char c, int estado_atual) {
  int proximo_estado = 9; // define o estado de erro como padrão.
  
  if (c == '+') {
    proximo_estado = AFD[estado_atual][0];
  } else if (c == '-') {
    proximo_estado = AFD[estado_atual][1];
  } else if (c == '.') {
    proximo_estado = AFD[estado_atual][2];
  } else if (isdigit(c)) {
    proximo_estado = AFD[estado_atual][3];
  } else if (c == 'e') {
    proximo_estado = AFD[estado_atual][4];
  } else {
    proximo_estado = AFD[estado_atual][5];
  }
  return proximo_estado;
}

int main(void) {
  const char * palavra = "+3.389E-10.8";
  int estado_atual = 0;
  int i;
  
  for(i = 0; i < strlen(palavra) && !isErro(estado_atual); i++) {
    printf("-- Estado atual: %d --\n", estado_atual);
    printf("Processando caractere: %c\n", palavra[i]);
    estado_atual = localizar_estado(tolower(palavra[i]), estado_atual);
  }
  
  if (i >= strlen(palavra) && !isFinal(estado_atual)) {
    printf("Palavra \t%s\t não aceita.", palavra);
  } else {
  
    if (isFinal(estado_atual)) {
      printf("Palavra \t %s \t %saceita.\n", palavra, isErro(estado_atual)? "não ":"");
    } else {
      printf("Palavra \t %s \t não aceita.\n");
    }
    
  }
  return 0;
}

 

Ajuda sim, muito obrigado!

 

Mas no caso, já solucionei o problema, conforme escrevi no post original, o único que ficou faltando foi a inserção do q7, a qual realizei depois, e solucionou o problema de ele (de alguma forma que eu não compreendi) estar no estado q9 e ir para o q5 (o que seria impossível, pois q9 não tem transição para q5)

Compartilhar este post


Link para o post
Compartilhar em outros sites

 

Sim, mas se você montar o autômato seguindo a tua tabela de transição, ele não vai fazer sentido nenhum porque a princípio, q7 é um estado inalcançável. Eu alterei os estados e a matriz de transição (ao invés de pular o q7 e ter somente o q8 e q9, mudei p/ q7 e q8) e alterei a condição do for do testeFinal (for(i = 0; i <= sizeof(estadoFinal)/sizeof(int) ; i++)).
Ele ainda processa o 'E' que está no expoente, mas atinge o -1 e recusa. O comportamento está certo. 
Agora, se você quer um autômato LR(1) a coisa vai ser mais complicada.

 


int estadoFinal[] = {3, 5, 8};
    int estadoIncial = 0;
    int i;
                                    //+ //- //. //E //Digito
   int tabelaTransicoes[9][5] =    {{1,  1,  2, -1,  3},  //q0
                                                 {-1, -1,  2, -1,  3},  //q1
                                                 {-1, -1, -1, -1,  5},  //q2
                                                 {-1, -1,  4,  6,  3},  //q3
                                                 {-1, -1, -1, -1,  5},  //q4
                                                 {-1, -1, -1,  6,  5},  //q5
                                                 { 7,  7, -1, -1,  8},  //q6
                                                 {-1, -1, -1, -1,  8},  //q7
                                                 {-1, -1, -1, -1,  8}}; //q8

 

Citar
Estado Inicial q0                                                                                                                                                                          
Caractere lido: 3                                                                                                                                                                          
   Transicao para q3 | Estado Final                                                                                                                                                        
Caractere lido: E                                                                                                                                                                          
   Transicao para q6 | Estado Nao-Final                                                                                                                                                    
Caractere lido: 2                                                                                                                                                                          
   Transicao para q8 | Estado Final                                                                                                                                                        
Caractere lido: E                                                                                                                                                                          
   Transicao invalida: Erro de leitura!                                                                                                                                                    
                                                                                                                                                                                           
A palavra 3E2E foi recusada pelo AFD!

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar Agora

  • Conteúdo Similar

    • Por EREGON
      Bom dia,
       
      estou a tentar fazer um exercício para, dado um ficheiro .txt na directoria do programa, terei de encontrar todas as palavras que são palíndromos. Tendo este código para ler as palavras do ficheiro .txt (letra a letra) para uma matrix.
       
      Estando as palavras armazenadas numa matrix, como faço essa validação?
       
      Obg,
       
      #include <stdio.h> #include <stdlib.h> int main(int argc, char const *argv[]) { FILE* inp; inp = fopen("palindromo.txt","r"); char arr[100][50]; int i = 0; while(1){ char r = (char)fgetc(inp); int k = 0; while(r!=',' && !feof(inp)){ //Le ate fim de ficheiro arr[i][k++] = r; //armazena no array r = (char)fgetc(inp); } arr[i][k]=0; //ultimo carater nulo //Alguma parte aqui, valida se a palavra e PALINDROMO. //COMO?? if(feof(inp)){ //valida EOF break; } i++; } int j; for(j = 0;j<=i;j++){ printf("%s\n",arr[j] ); //Imprime array } return 0; }  
    • Por Bruno Goedert Dalmolin
      Não consigo apresentar as palavras equivalentes conseguem me ajudar???
      O código é o seguinte: 
       
      #include <stdio.h>
      char equivale(int ddd){
          switch(ddd){
              case 61:
                  return "Brasilia";
                  break;
              case 71:
                  return "Salvador";
                  break;
              case 11:
                  return "Sao Palo";
                  break;
              case 21:
                  return "Rio de Janeiro";
                  break;
              case 32:
                  return "Juiz de Fora";
                  break;
              case 19:
                  return "Campinas";
                  break;
              case 27:
                  return "Vitoria";
                  break;
              case 31:
                  return "Belo Horizonte";
                  break;
          }
      }
      int main(){
          int ddd;
          scanf("%d",&ddd);
          equivale(ddd);
          printf("%d",equivale(ddd));
      }
    • Por darkskull10
      Numa cidade as crianças costumam brincar com um jogo (de dois jogadores) onde:
      um jogador A define uma sequência de 10 letras usando: G, R e B (exemplo: G – G – G – R – B – R – B – B – B – R)
      um jogador B pode ler a sequência quantas vezes quiser
      o jogador B também pode dizer uma das letras e obter em quais posições a letra dada se encontra na sequência
      o jogador B também pode dar uma posição e saber qual letra ocupa a posição na sequência
      para finalizar, o jogador B deve dizer a sequência de letras, obtendo um ponto para cada acerto.
       
      Só consegui pensar nisso por enquanto.
       
      //identificar que letra ocupa esta posição na sequência:
      do{
      scanf(“%d”,&Posicao);
      Posicao=Posicao-1;}
      while ((Posicao<0)||(Posicao>9));
      printf(“%c”,Sequencia[Posicao]);
       
      //exibir sequencia
      for (Cont=0; Cont<=9; Cont++)
      printf(“%c”,Sequencia[Cont]);
       
      //exibir posições
      for (Cont=0; Cont<=9; Cont++)
      printf(“%d%c”,Cont+1,Sequencia[Cont]);
    • Por lucas russo
      Boa noite ,pessoal não estou conseguindo resolver um exercício de algoritmo ,poderiam  me ajudar?
      Segue o exercício :
       
      Elabore um algoritmo que peça ao usuário que digite 1 numero maior que 500 retorne a soma dos fatoriais  de cada numero digitado compreendido  num inervá-lo de 2 números digitados .
    • Por EduardoLenz
      Olá, pessoal,
       
      Mexo com microcontroladores, antigamente com PIC e agora com ARM (plataforma LPCXpresso). 
      Ambos utilizam a linguagem C. 
       
      Meu problema é o seguinte: Preciso converter um caractere que vem da UART (porta de comunicação). No PIC havia uma função pronta para tal, no ARM não. 
       
      O caractere chega assim, por exemplo: P123 (tudo junto), e eu queria separar em:
      dado_recebido[]={'P', '1', '2', '3'}; 
      Para poder utilizar um switch 
      switch(dado_recebido[0])
      {
      case 'P':....
      }
       
      alguém tem alguma ideia de como posso fazer a conversão? 
       
      Agradeço desde já. 
×

Informação importante

Ao usar o fórum, você concorda com nossos Termos e condições.