Jump to content

KrilMun

Members
  • Content count

    5
  • Joined

  • Last visited

Community Reputation

0 Comum

About KrilMun

  1. KrilMun

    Algoritmo AFD

    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)
  2. KrilMun

    Algoritmo AFD

    Segue o diagrama de transições do AFD
  3. Bom dia amigos, Venho novamente requisitar seu auxílio, a fim de solucionar um problema proposto por meu professor, a saber: "Para cada linguagem a seguir apresente um AFD correspondente sobre Σ = {0, 1}. a) {α ∈ Σ* : α possui no mínimo três 0's e no mínimo dois 1's}. b) {α ∈ Σ* : α possui quantidade par de 0's e cada 0 é seguido por pelo menos um 1}." Onde Σ é o conjunto e α é a palavra. OBS: ∈ = pertence a O problema é que estou quebrando a cabeça com a questão A) desde ontem, e parece tão simples porém não consigo solucionar, pelo fato de pedir 2 condições simultaneamente. Por exemplo, a questão A) poderia ser quebrada nos 2 AFDs abaixo: Porém eu não posso simplesmente concatenar os 2 autômatos, porque se eu concatenasse o primeiro com o segundo, por exemplo, não poderia inserir a palavra válida 00011, pelo fato de ser obrigado a inserir pelo menos dois 1's para apenas a partir daí poder contar os 0's, ou mesmo palavras que apenas passassem por tais estados muito a frente, mas que seriam válidas para o enunciado da questão, como 00000100111. Da mesma forma, se eu concatenasse o segundo com o primeiro, palavras como 11000 não seriam aceitas, por ter que inserir pelo menos três 0's para contar os 1's. Não consigo pensar em uma forma de fazer um único autômato sem que haja Não Determinismo e/ou transições em vazio. Já a questão B) eu consegui fazer, ficando da seguinte forma: Mas a questão A) ainda está me dando um nó na cabeça hahaha Agradeço de antemão a ajuda!
  4. KrilMun

    Algoritmo AFD

    Agradeço pela explicação! Não sabia deste detalhe, ou talvez não lembrasse, estou meio enferrujado em C hahaha.. 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.
  5. KrilMun

    Algoritmo AFD

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

Important Information

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