Automato finito deterministico

Xandrules · 19 de setembro de 2016

Ola alguem poderia me dar uma ajuda de como eu codifico esse AFd?

vangodp · 20 de setembro de 2016

Amigo... explicar-te isso é algo complicado, aqui deixo um vídeo e o exemplo feito em C, o vídeo é para java, mas eu adaptei ele para C, acho que você não terá mais problemas. O programa tem um bug, por exemplo, se entramos com as palavras "char", "float" ou "for" as strings serão aceitadas, porém si complementamos essas palavras tipo "chart" ou qualquer outra letra em em vez de 't' o programa vai aceitar a string também, isso não deveria acontecer, mas acontece. Isso está acontecendo porque como bem podemos ver para analisar o string "char" passamos por q8, q9, q3 e por ultimo q4, o q4 é um nodo final, ele joga diretamente para qFinal que imprime a frase "aceitado pelo autômato", mas isso você teria que passar o sizeof da palavra para deter as comprovações justo na 'r' do "char" e caso o usuário tente por "chart" por exemplo, o programa não deve aceitar. Acho que você será capaz de arrumar esse pequeno problema, passando o sizeof desde main até a ultima função certo? Ou bem nessa qFim o ultimo char deveria ser o NULL que marca o fim da string, caso esse ultimo char não seja NULL é que tem mais letras que "char" e nesse caso a palavra é "char"+algo, e isso ta errado, deveria ir parar a qErro e não a qFim().

Deixo nas suas mãos arrumar esse "pequeno" bug >_<. O video ta aqui:
https://www.youtube.com/watch?v=cC8G0xZKqu8

E o programa adaptado ta aqui:

#include <stdio.h>
#define TAM 100

void qInicio ( char palavra[TAM]);
void q0( int contador, char palavra[TAM]);
void q1( int contador, char palavra[TAM]);
void q2( int contador, char palavra[TAM]);
void q3( int contador, char palavra[TAM]);
void q4( int contador, char palavra[TAM]);
void q5( int contador, char palavra[TAM]);
void q6( int contador, char palavra[TAM]);
void q7( int contador, char palavra[TAM]);
void q8( int contador, char palavra[TAM]);
void q9( int contador, char palavra[TAM]);
void qFim();
void qErro();

int main(){
    char palavra[TAM] = "for"; //casos de comprovação: 
    qInicio(palavra);
    
    return 0;
}

void qInicio ( char palavra[TAM] ){
    int contador = 0;
    q0( contador, palavra );
}

void q0( int contador, char palavra[TAM] ){
    if ( contador < TAM ){
        if ( palavra[contador] == 'f' ){
           q1( ++contador, palavra ); 

        }else if (palavra[contador] == 'c'){
           q8( ++contador, palavra ); 

        }else{
            qErro();
        }

    }
}

void q1( int contador, char palavra[TAM] ){
    if ( contador < TAM ){
        if ( palavra[contador] == 'l' ){
          q2( ++contador, palavra ); 

        }else if (palavra[contador] == 'o'){
           q3( ++contador, palavra ); 

        }else{
            qErro();
        }

    }
}

void q2( int contador, char palavra[TAM] ){
    if ( palavra[contador] == 'o' ) {
        q5 ( ++contador, palavra );
        
    } else {
        qErro();
    }
}

void q3( int contador, char palavra[TAM] ){
    if ( palavra[contador] == 'r' ) {
        q4 ( ++contador, palavra );
        
    } else {
        qErro();
    }
}

void q4( int contador, char palavra[TAM] ){
    qFim();
}

void q5( int contador, char palavra[TAM] ){
    if ( palavra[contador] == 'a' ) {
        q6 ( ++contador, palavra );
        
    } else {
        qErro();
    }
}

void q6( int contador, char palavra[TAM] ){
    if ( palavra[contador] == 't' ) {
        q7 ( ++contador, palavra );
        
    } else {
        qErro();
    }
}

void q7( int contador, char palavra[TAM] ){
    qFim();
}

void q8( int contador, char palavra[TAM] ){
    if ( contador < TAM ){
        if ( palavra[contador] == 'h' ){
          q9( ++contador, palavra ); 

        }else{
            qErro();
        }

    }
}

void q9( int contador, char palavra[TAM] ){
    if ( palavra[contador] == 'a' ) {
        q3 ( ++contador, palavra );
        
    } else {
        qErro();
    }
}


void qErro(){
    printf("Palavra regeitada pelo automata!\n");
}

void qFim(){
    printf("Palavra Aceita pelo automata!\n");
}

Se tiver duvidas pergunte.

Xandrules · 20 de setembro de 2016

Assim deu certo....

#include <stdio.h>
#include <string.h>
#define TAM 100

void qInicio ( char palavra[TAM],int size);
void q0( int contador, char palavra[TAM],int size);
void q1( int contador, char palavra[TAM],int size);
void q2( int contador, char palavra[TAM],int size);
void q3( int contador, char palavra[TAM],int size);
void q4( int contador, char palavra[TAM],int size);
void q5( int contador, char palavra[TAM],int size);
void q6( int contador, char palavra[TAM],int size);
void q7( int contador, char palavra[TAM],int size);
void q8( int contador, char palavra[TAM],int size);
void q9( int contador, char palavra[TAM],int size);
void qFim();
void qErro();

int main(){
	int size = 0;
    char palavra[TAM]; //casos de comprovação: 
    fflush(stdin);
    gets(palavra);
    
    while(palavra[size] != '\0')
    {
    	size++;    	
	}
    
    qInicio(palavra,size);
    
    return 0;
}

void qInicio ( char palavra[TAM],int size ){
    int contador = 0;
    q0( contador, palavra,size );
}

void q0( int contador, char palavra[TAM] ,int size){
    if ( contador < TAM ){
        if ( palavra[contador] == 'f' ){
           q1( ++contador, palavra,size ); 

        }else if (palavra[contador] == 'c'){
           q8( ++contador, palavra ,size); 

        }else{
            qErro();
        }

    }
}

void q1( int contador, char palavra[TAM] ,int size){
    if ( contador < TAM ){
        if ( palavra[contador] == 'l' ){
          q2( ++contador, palavra ,size); 

        }else if (palavra[contador] == 'o'){
           q3( ++contador, palavra,size ); 

        }else{
            qErro();
        }

    }
}

void q2( int contador, char palavra[TAM] ,int size){
    if ( palavra[contador] == 'o' ) {
        q5 ( ++contador, palavra,size );
        
    } else {
        qErro();
    }
}

void q3( int contador, char palavra[TAM] ,int size){
    if ( palavra[contador] == 'r' ) {
        q4 ( ++contador, palavra ,size);
        
    } else {
        qErro();
    }
}

void q4( int contador, char palavra[TAM] ,int size){
	if(contador == size)
	{
		qFim();
	}
    
    else
    {
    	qErro();
	}
    
}

void q5( int contador, char palavra[TAM] ,int size){
    if ( palavra[contador] == 'a' ) {
        q6 ( ++contador, palavra ,size);
        
    } else {
        qErro();
    }
}

void q6( int contador, char palavra[TAM] ,int size){
    if ( palavra[contador] == 't' ) {
        q7 ( ++contador, palavra ,size);
        
    } else {
        qErro();
    }
}

void q7( int contador, char palavra[TAM],int size ){
    if(contador == size)
	{
		qFim();
	}
    
    else
    {
    	qErro();
	}
}

void q8( int contador, char palavra[TAM] ,int size){
    if ( contador < TAM ){
        if ( palavra[contador] == 'h' ){
          q9( ++contador, palavra ,size); 

        }else{
            qErro();
        }

    }
}

void q9( int contador, char palavra[TAM] ,int size){
    if ( palavra[contador] == 'a' ) {
        q3 ( ++contador, palavra ,size);
        
    } else {
        qErro();
    }
}


void qErro(){
    printf("Palavra regeitada pelo automata!\n");
}

void qFim(){
    printf("Palavra Aceita pelo automata!\n");
}

adicionado 4 minutos depois

@vangodp Agora preciso fazer o mesmo usando fila e recursividade tem alguma dica ?
eu tenho que alocar cada estado ?

PauloPHFN · 4 de setembro de 2018

Bom dia;

Queria fazer esse exercício, porém nem sei por onde começa.

Este trabalho consiste de desenvolver um autômato finito determinístico em C++. O programa deve fazer a leitura da definição de um autômato (sempre lembrando que ele é determinístico) e em seguida uma lista de entradas que serão apresentadas ao autômato. Para cada das entrada deve-se imprimir ‘Aceita’ caso ao final do processamento da entrada um estado final esteja ativo, e ‘Rejeitada’ caso contrário. O autômato será descrito como um quíntupla. A primeira linha vai conter um inteiro n indicando a quantidade de estados, cada estado vai ser identificado de 0 a n-1. A segunda linha vai conter uma string de m caracteres, e cada carácter será um simbolo do alfabeto. A terceira linha terá um valor inteiro com a identificação do estado de início. A quarta linha terá uma série de números inteiro separados por carácteres de tabulação, representado o conjunto de estados finais. As próximas nxm linhas serão as transições de cada um dos estados na forma de uma tripla, portanto cada uma dessas linhas vai conter o identificador do estado atual, um simbolo do alfabeto e um identificador para o estado transicionado (todos separados por caracteres de tabulação). O restante das linhas são entradas apresentadas ao autômato.

Segundo a definição dada, o autômato a cima vai ser escrito como: 6 ab 0 2 5 0 a 1 0 b 3 1 a 3 1 b 2 2 a 5 2 b 4 3 b 2 3 a 4 4 a 4 4 b 4 5 a 4 5 b 4 E abaixo estão exemplos de entradas e saídas:a ab aab abb abba bb bba bbab Rejeitada Aceita Aceita Rejeitada Rejeitada Aceita Aceita Rejeitada Entradas Saídas