Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

bryanmg

Construir AFD em Python

Recommended Posts

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()

Share this post


Link to post
Share on other 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!!!!!

Share this post


Link to post
Share on other 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á?

Share this post


Link to post
Share on other 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()

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.