automa

#!/usr/bin/env python
#coding=utf8

'''
Lala

'''

class State(object):
	''' Représente un état de l'automate. '''
	
	def __init__(self, name):
		self.name = name

	def __repr__(self):
		return u'<State %s>' % self.name

class Transition(object):
	''' Représente une transition générique. '''
	
	__name__ = 'Transition'
	
	def __init__(self, state_from, state_to):
		self.state_from = state_from
		self.state_to = state_to

	def __repr__(self):
		return u'<%s-- %s -> %s-->' % (self.__name__, 
				self.state_from, self.state_to)


class NormalTransition(Transition):
	''' Représente une transition normale de l'automate. '''
	
	__name__ = 'NormalTransition'
	
	def __init__(self, state_from, state_to, labels):
		Transition.__init__(self, state_from, state_to)
		self.labels = labels


class EpsilonTransition(Transition):
	''' Représente une epsilon-transition de l'automate. '''

	__name__ = 'EpsilonTransition'


class Automaton(object):
	''' Représente un automate à états finis de Mealy. '''
	
	def __init__(self, alphabet, states=(), initial_states=(), 
									final_states=(), transitions=()):
		
		# L'alphabet Σ de l'automate :
		self.alphabet = set(alphabet)
		
		# Ses états Q (objets State) :
		self.states = set(states)
		
		# Ses états finaux Q_f (objets State) :
		self.final_states = set(final_states)
		
		# Et ses états initiaux Q_0 (objets State) :
		self.initial_states = set(initial_states)
		
		# Et ses transition δ (objets Transision) :
		self.transitions = set(transitions)
	
	def add_state(self, st):
		''' Ajouter un état à l'automate. '''
		self.states.add(st)
	
	def add_initial_state(self, st):
		''' Ajouter un état initial à l'automate. '''
		self.initial_states.add(st)
		
	def add_final_state(self, st):
		''' Ajouter un état final à l'automate. '''
		self.final_states.add(st)
	
	def add_transition(self, tr):
		''' Ajouter une transition à l'automate. '''
		self.transitions.add(tr)

	def leave(self, st):
		''' Méthode qui retourne toutes les transisions qui 
			partent de l'état state '''
		return set([t for t in self.transitions if t.state_from is st])

	def get_epsilons_states(self, etr):
		''' Retourne tous les états joints à une série 
			d'epsilon-transitions dont la première est passée en
			paramètres. '''

		st_to_travel = set((etr.state_to,)) # Les états à parcourir
		st_travelled = set() # Les états parcourus
		
		while st_to_travel:
			# On récupère un état que l'on a pas encore traité :
			state = st_to_travel.pop()
			
			# Par rapport à cet état, on récupère toutes les 
			# epsilons transition qui partent de cet état :
			tr_to_travel = set([tr for tr in self.leave(state) 
									if type(tr) is EpsilonTransition])
			
			# On ajoute tous les nouveaux états trouvés dans la liste
			# des états que l'on doit encore parcourir :
			st_to_travel |= (set([tr.state_to for tr in tr_to_travel]) 
														- st_travelled)
						
			# Enfin, on ajout l'état que l'on vient de parcourir dans
			# l'ensemble des états que nous avons parcouru :
			st_travelled.add(state)
		
		# On retourne tous les états qui ont été parcourus lors du
		# passage par les epsilons transitions :
		return st_travelled
			
	def acceptance(self, word):
		''' Retourne True si l'automate accepte le mot "word" passé en
			paramètre de la méthode. '''
		
		# Ensemble des états ou l'automate pouvait se retrouver lors de
		# la dernière itération sur le mot d'entrée. On initialise cet
		# ensemble avec l'ensemble des états initiaux pour commencer :
		states = self.initial_states
		
		# Itération sur chaque lettre du mot d'entrée :
		for f in word:
			
			# Initialisation de l'ensemble qui contiendra les états
			# parcourus pendant l'itération courante :
			next_states = set()
			
			# On parcourt les transitions de chaque état trouvé lors de
			# la dernière itération :
			for s in states:
				for tr in self.leave(s):
					
					# La transition peut être utilisée pour l'itération
					# courante du mot :
					if type(tr) == Transition and f in tr.labels:
						
						# Dans ce cas on ajoute l'état pointé par cette
						# transition dans l'ensemble des états à
						# parcourir à la prochaine itération :
						next_states.add(tr.state_to)
						
						# On ajoute aussi les états suivants pointés par
						# des epsilons-transitions :
						for etr in [t for t in self.leave(tr.state_to) 
									   if type(t) is EpsilonTransition]:
							next_states |= self.get_epsilons_states(etr)
							# !!! En Python, | est l'opérateur d'union
							#     des ensembles. (a |= b <-> a = a | b)
			
			# A la fin de chaque itération, on remplace l'ensemble des
			# états pour l'itération suivante :			
			states = next_states
			
		# Quand on a terminé d'itérer sur le mot, on retourne True si
		# des états sur lesquels nous sommes actuellement sont des états
		# finaux :
		return bool(states & self.final_states)
		# !!! En Python, & est l'opérateur d'intersection des ensembles.
	
	def empty_language(self, initial_states=None):
		''' Retourne True si l'automate possède un langage vide. 
			
			On parcourt l'automate en largeur pour vérifier que les
			états finaux sont atteignables.
			
			L'argument initial_states sert à indiquer des états initiaux
			à utiliser pour la recherche au lieu des états initiaux de
			l'automate (utilisé par la méthode infinite_language()). '''
		fifo = [] # La file du parcours en largeur
		st_travelled = set() # Ensemble des états déjà atteints
		
		# On initialise la file avec les états initiaux
		if initial_states:
			fifo += initial_states
		else:
			fifo += self.initial_states
		
		while fifo:
			state = fifo.pop(0) # On prend un élément de la file
			
			# Ajout de tous les états pointés par les transitions qui
			# quittent l'état courant si ils ne sont pas déjà dans la
			# liste des états à parcourir (pour éviter les boucles) :
			fifo += [tr.state_to for tr in self.leave(state) 
									if tr.state_to not in st_travelled]
			
			st_travelled.add(state)
		
		# Retourne True si les états qui nous avons parcourus ne sont
		# pas dans l'ensemble des états finaux :
		return not bool(st_travelled & self.final_states)
		
	def infinite_language(self):
		''' Returne True si l'automate possède un langage infini.
			
			La méthode recherche des boucles dans l'automate. Pour cela
			elle effectue un parcours en largeur de celui-ci en 
			gardant une référence vers chacun des états visités. Si un
			état est visité deux fois, c'est qu'une boucle a été
			trouvée. On vérifie alors si celle-ci est bien reliée à un
			état final, en utilisant la méthode empty_language en
			utilisant l'état visité une seconde fois comme état 
			initial. '''
		
		fifo = [] # La file du parcours en largeur
		st_travelled = set() # Ensemble des états déjà atteints
		
		# On initialise la file avec les états initiaux
		fifo += self.initial_states
		
		while fifo: 
			state = fifo.pop(0)
			
			for tr in self.leave(state):
				
				# L'état a déjà été vu (boucle detectée) :
				if tr.state_to in st_travelled:
					
					# On vérifie si cette boucle est bien reliée à un
					# état final :
					if not self.empty_language([tr.state_to]):
						return True
				else:
					# Sinon on ajoute l'état à la file pour le traiter
					# plus tard :
					fifo.add(tr.state_to)
			
			# Ajout de l'état courant à la liste des états parcourus :
			st_travelled.add(state)
			
		return False
			
	def render(self, filename):
		''' Générer une représentation du graphe de l'automate avec 
			l'outil Graphviz (necessite d'installer pygraphviz). '''
		
		try:
			import pygraphviz as gv
		except ImportError:
			print ('Il faut installer pygraphviz pour utiliser les '
					'méthodes de visualisation de l\'automate : '
					'easy_install pygraphviz')
		else:
			graph = gv.AGraph(directed=True)
			graph.add_nodes_from([n.name for n in self.states])
			graph.graph_attr['rankdir'] = 'LR'
			for st in self.final_states:
				n = graph.get_node(st.name)
				n.attr['shape'] = 'doublecircle'
			for st in self.initial_states:
				n = graph.get_node(st.name)
				n.attr['style'] = 'filled'
				n.attr['fillcolor'] = '#DDDDDD'
			for tr in self.transitions:
				if type(tr) is Transition:
					graph.add_edge(
						tr.state_from.name, 
						tr.state_to.name, 
						label=', '.join(tr.labels)
					)
				elif type(tr) is EpsilonTransition:
					graph.add_edge(tr.state_from.name, tr.state_to.name)
			graph.draw(filename, prog='dot')

	def __repr__(self):
		return u'<Automaton with %s states and %s transition>' % (
				len(self.states),
				len(self.transitions)
			)