quinta-feira, 19 de julho de 2007

Autômato Finito Determinístico

Seguindo a idéia de postar aqui assuntos relacionados ao mestrado, desta vez o post é sobre autômatos (automata), mais precisamente Autômatos Finitos Determinísticos - AFD (Deterministic Finite Automata - DFA), que estão sendo estudados na disciplina Análise de Algoritmos.

Segundo o Wikipédia, Autômato Finito Determinístico é uma máquina de estados finitos onde, para cada par de estados e símbolo de entrada, existe um próximo estado determinístico. A figura abaixo ilustra um AFD.



Como trabalho da disciplina tive que implementar um AFD que contemplasse os seguintes requisitos:
  • Receber como entrada os seguintes dados: (K, Σ, δ, s, F).
  • Os dados devem estar em formato texto.
  • O AFD deve informar se aceita ou rejeita a entrada informada.
Para quem tiver interesse, fiz um programa em Java para solucionar o problema proposto. O download é livre. Bom proveito!

Atualizado em 14/02/2011: O link para download do programa foi corrigido.

25 comentários:

Diogo Fontenele disse...

Boa noite amigo!
Rapáz to precisando aprender urgente sobre "Autômato Finito Determinístico" to com um trabalho p/ fazer da faculdade ele segue este mesmo projeto!
é um programa que receba como entrada uma definição de um autômato finito
determinístico e um conjunto de palavras para ser reconhecido pelo autômato.
Entrada: A Entrada é um arquivo txt contendo a descrição do autômato finito e uma seqüência de caracteres
e a associação ao autômato para serem verificadas no autômato finito. A entrada é da forma seguinte:
· Nome da Linguagem que o autômato reconhece.
· Alfabeto: símbolos separados por “;”.
· Conjunto de Estados separados por “;”.
· Estado Inicial.
· Conjunto de Estados Finais separados por “;”.
· Função de transição: Estado + “,” + símbolo do alfabeto + “=” + Novo Estado, cada item da função
de transição é separado por “;”
· Todos os itens são separados por “|”.
Saída: Um arquivo txt contendo a palavra que vai ser reconhecida e dizendo se “pertence” ou “não pertence”
a linguagem.
Exemplo
Entrada
L1|a;b|S0;S1;S2;S3|S0|S2|S0,a=S2;S0,b=S1;S1,a=S2;S1,b=S3;S2,a=S1;S2,b=S3;S3,a=S2;S3,b=S1
L1;aaa
L1;aabb
L1;aaabb
Saída
aaa não pertence a L1
aabb não pertence a L1
aaabb pertence a L1

Luciano Zanuz disse...

Amigo, essa definição é praticamente a mesma do programa que disponibilizei para download. Se quiseres, pode utilizá-lo como base para o seu. Uma diferença é que o meu programa, ao invés de ler um arquivo, o usuário deve informar as definições do autômato na tela.

Abraço

Diogo Fontenele disse...

Ok amigo, vou fazer uns testes aqui! Valeu!

Anônimo disse...

Olá Luciano, meu nome é Lucas e estou tb precisando aprender autômato finito deterministico, pois tenho um trabalho pra fazer.Se for possível,Gostaria de algumas dicas
=D
Descrição do trabalho:

Construir um programa em JAVA que possibilite a entrada de um “Autômato Finito Determinístico” com no máximo 10 estados e um alfabeto V com até 5 símbolos.

O programa deve possibilitar a entrada do autômato dinamicamente pelo usuário. Os seguintes dados devem ser lidos:

Número de estados: Por exemplo, se o número de estados for 5 então E = { q0, q1, q2, q3, q4 };
Alfabeto. Exemplo: V = { 0, 1};
Transições: Montar uma tabela onde o usuário deve fornecer os estados de transição. Por exemplo:

0 1
q0 q0 q1
q1 qrej q2
q2 qrej q3
q3 qrej q4
q4 q4 qrej

Em seguida solicitar 5 cadeias do usuário e analisar se são aceitas ou não utilizando o reconhecedor lido.

Possibilitar ao usuário entrar de 3 em 3 cadeias quantas vezes ele desejar.



Com esse programa q vc fez, da pra ter uma noção neh

abraço, vlww

Lucas Juren disse...

Olá Luciano,tudo bem?? estou tb precisando aprender autômato finito deterministico, pois tenho um trabalho pra fazer.Se for possível,Gostaria de algumas dicas
=D
Descrição do trabalho:

Construir um programa em JAVA que possibilite a entrada de um “Autômato Finito Determinístico” com no máximo 10 estados e um alfabeto V com até 5 símbolos.

O programa deve possibilitar a entrada do autômato dinamicamente pelo usuário. Os seguintes dados devem ser lidos:

Número de estados: Por exemplo, se o número de estados for 5 então E = { q0, q1, q2, q3, q4 };
Alfabeto. Exemplo: V = { 0, 1};
Transições: Montar uma tabela onde o usuário deve fornecer os estados de transição. Por exemplo:

0 1
q0 q0 q1
q1 qrej q2
q2 qrej q3
q3 qrej q4
q4 q4 qrej

Em seguida solicitar 5 cadeias do usuário e analisar se são aceitas ou não utilizando o reconhecedor lido.

Possibilitar ao usuário entrar de 3 em 3 cadeias quantas vezes ele desejar.



Com esse programa q vc fez, da pra ter uma noção neh

abraço, vlww

Luciano Zanuz disse...

Olá Lucas. Infelizmente estou completamente atarefado, tanto é que nem consigo atualizar o blog com a freqüência que gostaria.
O programa que eu disponibilizei para download tem mais ou menos as funcionalidades que você precisa, acredito que ele possa te ajudar. Além disso, tu podes encontrar muita informação na Web através do Google. Tenho certeza que vais conseguir!

Abraço e boa sorte!

ENFASE_PP disse...

O link para download do programa em java esta quebrado. Estou precisando analisar este codigo. Voce alguem poderia enviar para mim andreseven@gmail.com ou disponibilizar em algum lugar ?

Mariana disse...

Olá amigo, tdo bem?
estou fazendo um trabalho sobre autônomo determinístico e estou precisando dar uma olhada neste código q vc disponibilizou para download, porém, o link está com problemas. Você poderia repassar o link para meu endereço de email: marianaoliveirasi@gmail.com
muito obrigada
abraços....

rafael disse...

Cara eu tambem to precisando desse codigo fonte mas o link tah quebrado se tu poderes mandar pro meu e-mail eu agradeceria!!!

Vai ai o e-mail: rafael_mathias89@hotmail.com

Valeuu!!!

Anônimo disse...

Oi galera!

Meu problema não é tão diferente não minha dificuldade tá em transformar um automato finito não deterministico com transições vazias em um afn sem transições vazias quem puder me dá uma ajuda pra enternder esse processo eu agradeço.

pattyrds@msn.com

Anônimo disse...

teria como me enviar o codigo?
agradeco
fe_gabo@hotmail.com

Anônimo disse...

Tem como me enviar o código?
Obrigada
kaie_ka@yahoo.com.br

Anônimo disse...

Luciano.
Voce pode enviar o codigo?
lucadimafi@gmail.com
Grato.

Anônimo disse...

Boa tarde,
Estou precisando desse codigo Voce poderia enviar para mim.
Obrigada,
criscrisrr@hotmail.com

Anônimo disse...

Boa tarde,

Eu estou precisando fazer um trabalho, implementar um programa que seja capaz de executar o funcionamento de um AFD.
Entradas sugeridas: AFD + Palavra
Saida desejada: aceita/ não aceita.
Gostaria de algumas dicas para poder começar a fazer o trabalho.
Obrigada,
criscrisrr@hotmail.com

Fernando disse...

Boa tarde, o link não existe mais.
Estou precisando desse codigo Voce poderia enviar para mim.
Obrigado,
alvesfmoreira@gmail.com

Wagner disse...

Luciano, boa noite! O link a se refere ao tópico ""Automato Finito Determinístico" está quebrado. É possível me enviar o código? Tenho um trabalho a fazer que é muito parecido. Obrigado! E-mail: martins.bibiano@gmail.com

sagui disse...

Ola Luciano, poderia enviar o codigo no meu email:
lgribeiro.info@gmail.com
Att

Paulo disse...

Oi,

minha dúvida é a seguinte:

Autômato Finito Determinístico pode possuir loop?

Agredecido,
Paulo Cordeiro.

Pêga disse...

Ola, tentei fazer o download, mas o link esta quebrado, manda pro meu email(wesley_pga@yahoo.com.br) o rmais rapido possivel, desde já, grato!!

Luciano Zanuz disse...

Atualizado em 14/02/2011: O link para download do programa foi corrigido.

LICO disse...

Boa tarde, Luciano!!!
Estou precisando fazer um trabalho que implemente um programa que verifique a ocorrência de uma palavra dentro de um arquivo texto através do uso de Autômatos Finitos Determinísticos (AFD’s). As entradas deste programa são o nome do arquivo texto e a palavra a ser pesquisada. A saída gerada pelo programa são o número de ocorrências da palavra e as respectivas posições onde foi encontrada no texto (linha e coluna = caracteres a partir do início da linha).
Se conseguir me dar uma ajuda fico grato, pois estou bem perdido nessa parte.
Att.
Tiago Helmich

Ricardo disse...

Olá Luciano, baixei o seu software e estou estudando ele e tentando entender, mas me deparei com uma dúvida: Ele não precisa de uma class main para poder executar? Porque se eu tento executar a class que esta disponível, AutomatoAFD ela dá um erro, só funciona a AutomatoAFD.jar, sou novato em programação e agradecia que pudesse dar um help, outra situação é, não entendi o comando append que usou na varável jTextAreaResultados.append ele é uma classe? Eu tentei usar o mesmo comando no software que estou tentando fazer e da erro, daí não consegui resolver isso, então tirei o append e criei uma declarei uma String, e coloquei jTextAreaResultados.settext ao em vez de append mas aí o na hora de tornar ele uma aplicação.jar o arquivo não executa e não fica com .jar isso na pasta dist do projeto. Já usei o google para puder entender e nada. Obrigado

Ricardo disse...

Olá Luciano, baixei o seu software e estou estudando ele e tentando entender, mas me deparei com uma dúvida: Ele não precisa de uma class main para poder executar? Porque se eu tento executar a class que esta disponível, AutomatoAFD ela dá um erro, só funciona a AutomatoAFD.jar, sou novato em programação e agradecia que pudesse dar um help, outra situação é, não entendi o comando append que usou na varável jTextAreaResultados.append ele é uma classe? Eu tentei usar o mesmo comando no software que estou tentando fazer e da erro, daí não consegui resolver isso, então tirei o append e criei uma declarei uma String, e coloquei jTextAreaResultados.settext ao em vez de append mas aí o na hora de tornar ele uma aplicação.jar o arquivo não executa e não fica com .jar isso na pasta dist do projeto. Já usei o google para puder entender e nada. Obrigado

Ricardo disse...

Olá Luciano, baixei o seu software e estou estudando ele e tentando entender, mas me deparei com uma dúvida: Ele não precisa de uma class main para poder executar? Porque se eu tento executar a class que esta disponível, AutomatoAFD ela dá um erro, só funciona a AutomatoAFD.jar, sou novato em programação e agradecia que pudesse dar um help, outra situação é, não entendi o comando append que usou na varável jTextAreaResultados.append ele é uma classe? Eu tentei usar o mesmo comando no software que estou tentando fazer e da erro, daí não consegui resolver isso, então tirei o append e criei uma declarei uma String, e coloquei jTextAreaResultados.settext ao em vez de append mas aí o na hora de tornar ele uma aplicação.jar o arquivo não executa e não fica com .jar isso na pasta dist do projeto. Já usei o google para puder entender e nada. Obrigado