Simula Autômato Determinístico

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

##########################################################################
# DIEGO PEDRO GONCALVES DA SILVA 20911057 #
# Data = 06/03/2011 # 
##########################################################################
class Automato:
 estados = None
 EstadoInicial = None
 EstadosFinais = None
 def __init__(self, estados, EstadoInicial, EstadosFinais):
 self.estados = estados
 self.EstadoInicial = EstadoInicial
 self.EstadosFinais = EstadosFinais
 
 def ehEstadoFinal(self, estado):
 for qf in self.EstadosFinais:
 if qf == estado:
 return True
 return False 
		
 def simula(self, estadoAtual, palavra, indice):
 
 print "%sq(%s,%s)" %('-'*(indice*3),estadoAtual,palavra[indice])
 #se ja leu a fita 
 if(indice+2 > len(palavra)):
 if estadoAtual == "VAZIO": #se o arco nao existe EX A{a},C{b}
 return False
 
 elif self.ehEstadoFinal(estadoAtual):
 return True
 
 return False #nao esta em um estado final
 
 elif estadoAtual == "VAZIO":# a fita ainda nao acabou porem
 return False # foi lido um simbolo que o automato
 # nao pode processar no estado atual
 else: 
 est_resultado = False
 
 #verifica todos os arcos do estado atual e percorre
 #um por um recursivamente
 for estado in self.estados[estadoAtual][palavra[indice]]:
 est = self.simula(estado,palavra, indice + 1)
 if est == True: #basta apenas atingir um estado final
 est_resultado = True
 return est_resultado
			
 def run(self,palavra):
 print palavra
 print self.simula(estadoInicial, list("x"+palavra), 1),"\n",'_'*30
 
 	
#-----------------automato--do--problema--10-------------------
A = {'a':["VAZIO"],'b':['B','C']} 
B = {'a':['C','D'],'b':["VAZIO"]}
C = {'a':['D'],'b':["VAZIO"]}
D = {'a':["VAZIO"],'b':["VAZIO"]}
estados ={'A':A,'B':B,'C':C,'D':D}
estadosFinais = ['D']
estadoInicial = 'A'
A = Automato(estados, estadoInicial, estadosFinais)
#Exemplo
A.run('baa')
A.run('b')
A.run('bb')
A.run('baaa')
A.run('baaa')