Afd

[hpt 0]

Pessoal, estou na 4ª fase de sistemas de informação e o professor começou a explicar sobre AFD e pediu que a gente faça um AFD em qualquer linguagem de programação,ele pediu um que reconheça {x E {0,1,2,3,4,5,6,7,8,9}*| x representa um numero decimal divisivel por 3}, mas nao quero o programa exatamente pronto pois quero aprender( mas se quiserem dar ele pronto tambem aceito porque depois te um muito mais dificil), ou podem mandar um de numeros multiplos de qualquer numero, sei la, mas gostaria de um exemplo por que nao tenho nem ideia de como começar, ja que ele nao deu exemplo nenhum, desde ja eu agradeço.

obrigado

[Renato Utsch 24]

Bom, se você não quer o programa pronto, então você não quer exemplos. Se você quer, você quer exemplos. Me parece que você está pedindo pelo programa pronto, ou foi só impressão minha?

 

Anyway, eu não entendi o que você quer fazer, eu não sou (e ninguém é) obrigado a conhecer o que é um AFD. Poderia nos explicar para que possamos te ajudar melhor?

 

 

Abraços :D

[hpt 0]

beleza, entao quero um exemplo sim de AFD(autonato finito deterministico), pra mim ver em funcionamento por que nao tenho nenhuma ideia de como funciona na pratica, pode ser em C ou em Java.

obrigado.

[Renato Utsch 24]

Olá!

 

Primeiro, não faremos seu dever de casa, não vamos te dar um programa pronto. Segundo, você não respondeu minha segunda pergunta, como podemos te ajudar?

 

 

Abraços :D

[hpt 0]

o trabalho de casa é um programa especifico e nao um qualquer, eu quero um qualquer pra mim ver o funcionamento de um AFD(aumato finito deterministico).

Definição. Um Autômato Finito Determinístico (afd) M, sobre um alfabeto S é um

sistema (K, S, d, i, F), onde

K é um conjunto de estados finito, não vazio;

S é um alfabeto de entrada (finito)

d: K´S ® K é a função de transição

iÎK é o estado inicial

FÍK é o conjunto de estados finais.

O nome determinístico faz referência ao fato de que d é uma função (também

chamada função próximo-estado), que determina precisamente o próximo estado a ser

assumido quando a máquina M se encontra no estado q e lê da entrada o símbolo a: o

estado d(q, a).

[guidjos 65]

Não é complicado. Parece que seu professor não especificou como a entrada deve ser feita, então você pode muito bem usar tipos inteiros pra representar 1, 2, 3, 4, 5, 6, 7, 8 e 9.

 

x E {1, 2, 3, 4, 5, 6, 7, 8, 9}*, ou o "fecho" de {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, são todas as cadeias que se pode formar com seus elementos, mais a cadeia vazia. A restrição de que o número representado pela cadeia seja divisível por três é facilmente checada em C, se a entrada puder ser representada com um tipo inteiro qualquer (como unsigned char, unsigned short, unsigned int, unsigned long int, unsigned long long int). Se ela tiver que ser lida em forma textual, você pode usar strtol.

 

Note que o conjunto definido de cadeias é infinito, portanto é impossível criar um programa que realmente reconheça qualquer cadeia pertencente a ele. Usando unsigned long long int, é garantido que você conseguirá representar até 2^64 - 1 (no mínimo). Daí, como eu disse anteriormente, basta usar o operador de módulo.

 

Se precisar trabalhar com valores maiores, use um array de char, lendo os dígitos byte a byte e usando o fato de que a divisibilidade por 3 se dá se e somente se a soma dos números formados por cada algarismo que compõe a representação de cada uma das ordens de grandeza do número divisível for, também, divisível por 3. Você pode converter cada dígito lido e somá-lo a um total, que deve, ele mesmo, ser divisível por 3.

[hpt 0]

isso, ele falou que a implementação é livre,mas que temos que fazer a maquina de estados para mostrar todos os estados, mas nao tenho nem ideia de como isso funcionara em C ou Java.

 

ele pediu um que mostre um numero divisivel por 3, mas se tiver um que reconheça numeros pares tambem pode ser, só pra mim ter uma ideia de como começar {0,1,2,3,4,5,6,7,8,9}, sao as entradas.

[guidjos 65]

A seguinte rotina retorna um valor diferente de 0 se seu argumento (inteiro) é divisível por 3:

 

int div3(int numero)
{
   return !(numero % 3);
}

/* Exemplo de uso:

if (div3(15))
{
   puts("15 % 3 == 0");
}

*/

 

Seu autômato pode ser representado de diversas formas. Os estados e transições podem ser implícitos ou explícitos. Se quiser deixar mais claras suas intenções, defina estruturas de dados e rotinas que as manipulem explicitamente.

[hpt 0]

Esse que você fez foi em C++ né? tipo aquele que o professor pediu era pra ler digito por digito e dependendo se fosse divisivel ou nao, ele passaria para um determinado estado, mas esse que você ja deu uma ideia.

[Renato Utsch 24]

Olá!

 

Sim e não.

 

Foi código escrito em C++. Mas também foi escrito em C. A parte de funções, na maioria dos recursos disponíveis, pode ser implementado igualmente para as duas linguagens. No caso, é um código em C que pode ser usado em C++.

 

A função que o guidjos passou retornava {nº diferente de 0} se o número era divisível por 3 e 0 se ele não era. Não era isso o que queria?

 

 

 

Abraços :D

[hpt 0]

sim,mas por exemplo, se for digitado 568726, tem que verificar digito por digito e ir trocando de estado na maquina de estados.

[Renato Utsch 24]

Você sabe como verificar dígito por dígito? Divida o número como inteiro por 10, você vai ter 1 dígito a menos. Então, se, por exemplo, testar o número 4506, é só dividir ele como inteiro por 1000, aí o resultado vai ser 4, que pode testar com a função do guidjos. Enton divida por 100 e subtraia o dígito anterior multiplicado por 10, e continue assim, até conseguir todos...

 

Deve ter modos mais fáceis, se não estou enganado tem uma função da standard para isso e, se não, pode usar uma função da standard que converte o número para caracteres, aí fica mais fácil de checar dígito por dígito.

 

 

 

Abraços :D

[guidjos 65]

Seu professor provavelmente quer que a verificação da divisibilidade seja explicitada nos estados do autômato. Sugiro, então, que primeiro concentre-se em representar os conceitos necessários a todos os autômatos, pra depois focar na funcionalidade deste em específico. Modele estruturas de dados para representação de um estado, de um terminal de entrada e de uma regra de transição.

 

Sempre que estiver modelando qualquer tipo de dados, sugiro que pense primeiro nas operações que ele suportará. Isso lhe permitirá estruturar a abstração de modo que as operações possam ser feitas de forma intuitiva (com respeito à linguagem de programação em si). Você precisará, por exemplo, ler um terminal e aplicar uma regra de transição (usualmente modelado como uma função, e usualmente com nome 'lambda').

 

Apresente sua modelagem aqui, pra que possamos aconselhá-lo.

[hpt 0]

caramba, quanto mais eu tento entende, mais dificil fica, mas beleza, vo tenta desenvolve alguma coisa aqui, pra ver se consigo, mas to vendo que vai ser complicado, nem eu entendi o que ele tava pedindo no enunciado do exercicio. :P

[guidjos 65]

Se você sabe o que é um AFD, não é difícil resolver o problema. AFDs são máquinas simples. Trabalhe no que eu disse e pergunte aqui se tiver alguma dúvida.