Jump to content
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..

Edited by KrilMun
EDIT 2: Resolução do problema.

Share this post


Link to post
Share on other 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))

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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".

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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;
}

 

Share this post


Link to post
Share on other 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)

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Similar Content

    • By Elizandro Veloso
      Preciso de ajuda em um projeto, esse projecto , precisa alterar, guardar as fichas, como  faço para alterar, guardar etc ?
       
      switch(menu) { case 'c': case 'C': printf("\n-----------------------------------------------------------\n"); printf("\t\t Ficha de Componentes\n"); printf("-----------------------------------------------------------\n"); componente = inserirComponente(componente); break; case 'p': case 'P': printf("\n-----------------------------------------------------------\n"); printf("\t\t Posto de Trabalho\n"); printf("-----------------------------------------------------------\n"); posto = inserirPostoTrabalho(posto); break; case 'f': case 'F': printf("\n-----------------------------------------------------------\n"); printf("\t\t Ficha de Funcionário\n"); printf("-----------------------------------------------------------\n"); funcionario = inserirFuncionario(funcionario); break; case 'o': case 'O': printf("\n-----------------------------------------------------------\n"); printf("\t\t Ficha das Operações\n"); printf("-----------------------------------------------------------\n"); operacao = inserirOperacao(operacao); break; case 'e': case 'E': printf("\n-----------------------------------------------------------\n"); printf("\t\t Ficha de Empresa\n"); printf("-----------------------------------------------------------\n"); empresa = inserirEmpresa(empresa); break; case 's': case 'S': printf("\n-----------------------------------------------------------\n"); printf("\t\t Obrigado e volte sempre\n"); printf("-----------------------------------------------------------\n"); break; default: printf("\n---------------------------------------------------------------\n"); printf("\t\t A instruçao inserida não existe no Menu!!\n\n\t\t Aguarde para digitar novamente...\n"); printf("-----------------------------------------------------------------\n"); sleep(4); system("cls"); } }while(menu != 'S' && menu != 's');
       
    • By roberson abalaid
      #include <stdio.h>
      #include <stdlib.h>
      int arr[3][5];
      int main(){
          
          printf("Favor inserir os dados...\n");
          
          for(int i = 0; i < 3; i++){
              for(int j = 0; j < 5; j++){
                  scanf("%d", &arr[j]);
              }
          }
          
            printf("os valores inseridos foram...\n");
          
          for(int i = 0; i < 3; i++){
              for(int j = 0; j < 5; j++){
                  printf("  %d  ", arr[j]);
              }
              printf("\n");
          }
          return 0;
      }
    • By marceloDiegues
      Olá, amigos.
      Por favor,  me ajude com a seguintes perguntas.
       
      Qual a complexidade de um projeto desse?
      Qual o preçp de um projeto desse tipo?
       
      Quero contratar algum profissional para criar um site que tenha as seguintes funcionabilidades:
       
      1- Cadastro de usuário;
      2- Login e senha;
      3- O site seria muito parecido com o www.qconcursos.com, o usuário resolveria questões online.
      Contudo, haveria a possibilidade de criar salas tipo aqueles bate-papo da &nbsp;UOL.
      Então, o usuário criaria salas de estudos, em que , resolveria questões e conseguiria se comunicar por chat com usuários que estejam na mesma sala.
       
      Exemplo em anexo:
       
       
       
       

    • By Motta
      O algoritmo que procura padrões ocultos na maior base de dados de sonhos do mundo
    • By IgorExtreme
      Olá estou com problema nesta questão: "Escreva um programa que leia e armazene em um vetor os dados de 30 pessoas. Estes dados são o nome da pessoa, sua idade, e os nomes completos do pai e da mãe. A seguir, o programa deve identificar (e mostrar os índices) das pessoas que estão relacionadas por um parentesco avô-neto e irmão-irmão. No caso dos irmãos, deve ser informado ainda qual é o mais novo dos dois." O código é esse
      #include<stdio.h> #include<string.h> #define NUM 4 struct pessoa { char nome[20]; char mae[20]; char pai[20]; int idade; }; main() { struct pessoa vetorPessoas[NUM]; int i; printf("Digite os dados de %d pessoas:\n", NUM); for (i = 0; i < NUM; i++) { printf("Digite o nome da pessoa %d: ", i); fflush(stdin); gets(vetorPessoas[i].nome); printf("%s\n", vetorPessoas[i].nome); printf("Digite o nome da mae da pessoa %d: ", i); fflush(stdin); gets(vetorPessoas[i].mae); printf("%s\n", vetorPessoas[i].mae); printf("Digite o nome do pai da pessoa %d: ", i); fflush(stdin); gets(vetorPessoas[i].pai); printf("%s\n", vetorPessoas[i].pai); printf("Digite a idade da pessoa %d: ", i); fflush(stdin); scanf("%d", &vetorPessoas[i].idade); printf("%d\n", vetorPessoas[i].idade); if(!strcmp(vetorPessoas[0].pai, vetorPessoas[1].nome)){ printf("%s e avo de %s\n", vetorPessoas[1].pai, vetorPessoas[0].nome); } if(!strcmp(vetorPessoas[2].pai, vetorPessoas[3].nome)){ printf("%s e avo de %s\n", vetorPessoas[3].pai, vetorPessoas[2].nome); } } /*if(!strcmp(vetorPessoas[i].pai, vetorPessoas[i].nome)){ printf("%s e pai de %s\n", vetorPessoas[i].pai, vetorPessoas[i].pai); }*/ if(!strcmp(vetorPessoas[0].pai, vetorPessoas[1].pai)){ printf("Eles sao irmaos\n"); if(vetorPessoas[0].idade > vetorPessoas[1].idade){ printf("%s mais velho\n", vetorPessoas[0].idade); } else{ printf("%s e mais novo\n", vetorPessoas[1].idade); } } if(!strcmp(vetorPessoas[2].pai, vetorPessoas[3].pai)){ printf("Eles sao irmaos\n"); if(vetorPessoas[2].idade > vetorPessoas[3].idade){ printf("%s mais velho\n", vetorPessoas[2].idade); } else{ printf("%s e mais novo\n", vetorPessoas[3].idade); } } } O problema é que ele mostra quase tudo menos a parte se tal irmão é mais velho que o outro
×

Important Information

Ao usar o fórum, você concorda com nossos Terms of Use.