Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

bryanmg

Construir AFD em Python

Mensagens Recomendadas

bryanmg

Galera Tô precisando de uma ajuda,  Preciso construir esse AFD abaixo em python.

Esse programa tem que ler um arquivo de entrada, que em cada linha

há uma palvra composta de 0 ' s  ou 1 's.

Gravar um arquivo de saída onde em cada linha é registrada a seqüência de estados pelos quais a máquina passou e por fim um caracter S ou N, indicando se a palavra foi reconhecida pelo AFD ou não.

Fiz o código abaixo com a ajuda de uns amigos mas ta dando uns erros.

Será que alguém pode me ajudar.

automato.jpg

# coding=latin-1
estados = ['A','B','C','D']
alfabeto = set(['0', '1'])
transicoes = {'A' : {'1' : 'A', '0' : 'B'},'B' : {'0' : 'B', '1' : 'C'}, 'C' : {'0' : 'C', '1' : 'D'},
'D' : {'0' : 'B', '1' : 'D'}  }
estadoInicial = 'A'
estadoFinal = ['A','D']

def usaAfd(palavra):
      estadoAtual = estadoInicial # Estabelece o estado inicial 
para efetuar a primeira verificação de troca de estado
      pF = estadoAtual # Inicia a palavra final com o estado inicial
      for b in palavra:
           estadoAtual = afd[estadoAtual, int(b)] # Busca o estado resultante da troca de estado no dicionario da afd
           pF = pF + estadoAtual # Concatena as strings para formar a palavra final

      # Verifica se a palavra foi aceita ou nao pelo AFD
      if estadoAtual == estadoFinal:
            pF = pF + 'S'
      else:
            pF = pF + 'N'
      return pF

# Abrindo arquivo de saida
arqSaida = open("saida.txt","w")
# Abrindo arquivo de entrada    
arqEntrada = open("entrada.txt","r")
ln = arqEntrada.readline()
while len(ln) > 0:
    print "Palavra de Entrada:",ln
    palavraFinal = usaAfd(ln.strip()) # Remove espaços antes e d
epois da palavra e envia para o afd
    print "Palavra final:", palavraFinal
    print "------------------------------------------"
    arqSaida.write(palavraFinal+"\n")   # Grava a palavra final no 
arquivo de saida e muda de linha
    ln = arqEntrada.readline()

print "Arquivo gravado com sucesso"

# Fecha os arquivos abertos    
arqEntrada.close()
arqSaida.close()

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
bryanmg

o Erro é o seguinte, fiz as transições do AFD, no codigo em python, mas não sei se as transições estão certas e outra coisa quando rodo o mesmo, da um problema nas linhas 13 e 30 não sei como consertar.

E outra coisa, ao termino da execução aparece que o arquivo foi gravado com sucesso.

Não sei como posso fazer isso, me ajuda por favor!!!!!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
JoaoRodrigues

Bem, do código que aí tens eu digo-te dois problemas: chamas a lista afd e nunca a crias, na mesma linha estás parece-me a fazer um splice muito esquisito.

Que erro em concreto te dá?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
bryanmg

Desculpe estar incomodando denovo, dei uma melhorada no código que eu postei primeiro , agora ele funciona, gera o arquivo de saída, mas não consigo fazer que as palavras sejam reconhecidas.

Por exemplo seguindo a execução, se no arquivo txt de entrada estiver o numero 1 a saída deverá ser AAS, mas está gerando sáida AAN.

Alguém poderia me ajudar!!!

# coding=latin-1

estadoInicial = 'A'
estadoFinal = 'A', 'D'
afd = {('A',0):'B',('A',1):'A',('B', 0): 'B',('B',1):'C',('C',0): 'C',('C',1):'D',('D',0):'B',('D',1):'D',}

def usaAfd(palavra):
      estadoAtual = estadoInicial # Estabelece o estado inicial para efetuar a primeira verificação de troca de estado
      pF = estadoAtual # Inicia a palavra final com o estado inicial
      for b in palavra:
           estadoAtual = afd[estadoAtual, int(b)] # Busca o estado resultante da troca de estado no dicionario da afd
           pF = pF + estadoAtual # Concatena as strings para formar a palavra final

      # Verifica se a palavra foi aceita ou nao pelo AFD
      if estadoAtual == estadoFinal:
            pF = pF + 'S'
      else:
            pF = pF + 'N'
      return pF

# Abrindo arquivo de saida
arqSaida = open("saida.txt","w")
# Abrindo arquivo de entrada    
arqEntrada = open("entrada.txt","r")
ln = arqEntrada.readline()
while len(ln) > 0:
    print "Palavra de Entrada:",ln
    palavraFinal = usaAfd(ln.strip()) # Remove espaços antes e depois da palavra e envia para o afd
    print "Palavra final:", palavraFinal
    print "------------------------------------------"
    arqSaida.write(palavraFinal+"\n")   # Grava a palavra final no arquivo de saida e muda de linha
    ln = arqEntrada.readline()

print "Arquivo gravado com sucesso"

# Fecha os arquivos abertos    
arqEntrada.close()
arqSaida.close()

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.