automate.py

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

from automatelib import State, Transition, Automaton, EpsilonTransition


if __name__ == '__main__':
	# Automate de test acceptant l'alphabet {a, b, c} et dont les mots
	# commencent et finissent forcément par a.
	#~ s1 = State('1')
	#~ s2 = State('2')
	#~ s3 = State('3')
	#~ s4 = State('4')
	#~ s5 = State('5')
	#~ s6 = State('6')
	#~ s7 = State('7')
	#~ s8 = State('8')
	#~ s9 = State('9')
	#~ s10 = State('10')
	#~ a = Automaton('abc', 
		#~ states=(s1, s2, s3, s4, s5, s6, s7, s8, s9, s10), 
		#~ initial_states=(s1, s2, s3), 
		#~ final_states=(s7, s8, s9)
	#~ )
	#~ 
	#~ a.add_transition(Transition(s1, s1, 'abc'))
	#~ a.add_transition(Transition(s1, s4, 'a'))
	#~ a.add_transition(Transition(s4, s4, 'abc'))
	#~ a.add_transition(Transition(s4, s7, 'a'))
	#~ 
	#~ a.add_transition(Transition(s2, s2, 'abc'))
	#~ a.add_transition(Transition(s2, s5, 'b'))
	#~ a.add_transition(Transition(s5, s5, 'abc'))
	#~ a.add_transition(Transition(s5, s8, 'b'))
#~ 
	#~ a.add_transition(Transition(s3, s3, 'abc'))
	#~ a.add_transition(Transition(s3, s6, 'c'))
	#~ a.add_transition(Transition(s6, s6, 'abc'))
	#~ a.add_transition(Transition(s6, s9, 'c'))
#~ 
	#~ a.add_transition(EpsilonTransition(s1, s10))
	#~ a.add_transition(EpsilonTransition(s10, s7))
	
	a = State('a')
	a2 = State('a2')
	
	b1 = State('b1')
	b2 = State('b2')
	b3 = State('b3')
	
	found = State('found')
	deuxieme = State('deuxieme')
	
	da1 = State('da1')
	da11 = State('da11')
	da12 = State('da12')
	da13 = State('da13')
	
	done = State('done')
	anothera = State('anothera')
	
	automaton = Automaton('ab',
		states = (a, a2, b1, b2, b3, found, deuxieme, da1, da11, da12, da13, done, anothera),
		initial_states = (a,),
		final_states = (found, )
	)
	automaton.add_transition(Transition(a, a, 'ab'))

	automaton.add_transition(Transition(a, b1, 'a'))
	automaton.add_transition(Transition(b1, b2, 'b'))
	automaton.add_transition(Transition(b2, b3, 'b'))
	automaton.add_transition(Transition(b3, a2, 'a'))
	automaton.add_transition(Transition(a2, found, 'a'))

	automaton.add_transition(Transition(found, found, 'b'))
	automaton.add_transition(EpsilonTransition(found, deuxieme))

	automaton.add_transition(Transition(deuxieme, da1, 'a'))
	automaton.add_transition(EpsilonTransition(da1, da11))
	automaton.add_transition(EpsilonTransition(da11, da12))
	automaton.add_transition(EpsilonTransition(da12, da13))
	automaton.add_transition(EpsilonTransition(da1, da13))
	automaton.add_transition(Transition(da13, done, 'a'))
	automaton.add_transition(Transition(da12, found, 'a'))

	automaton.add_transition(Transition(done, anothera, 'a'))

	automaton.add_transition(EpsilonTransition(anothera, a2))
	automaton.add_transition(Transition(anothera, da12, 'a'))

automatelib.py

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

class State(object):
	'''
		Classe définissant un état
	'''
	
	def __init__(self, name):
		
		self.name = name

	def __repr__(self):
		return u'<State %s>' % self.name
		
class Transition(object):
	'''
		Classe définissant une transition
	'''
	
	def __init__(self, state_from, state_to, labels):
		
		self.state_from = state_from
		self.state_to = state_to
		self.labels = labels

	def __repr__(self):
		return u'<Transition %s -> %s labeled %s>' % (self.state_from, 
								self.state_to, ', '.join(self.labels))

class EpsilonTransition(Transition):
	'''
		Classe définissant une Epsilon transition
	'''
	
	def __init__(self, state_from, state_to):
		
		self.state_from = state_from
		self.state_to = state_to

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

class Automaton(object):
	'''
		Classe définissant un Automate Fini A
	'''
	
	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, state):
		'''
			Ajouter un état à l'automate.
		'''
		
		self.states.add(state)
	
	
	def add_initial_state(self, state):
		'''
			Ajouter un état initial à l'automate
		'''
		
		self.initial_states.add(state)
		
		
	def add_final_state(self, state):
		'''
			Ajouter un état final à l'automate
		'''
		
		self.final_state.add(state)
	
	
	def add_transition(self, transition):
		'''
			Ajouter une transition à l'automate
		'''
		
		self.transitions.add(transition)


	def leave(self, state):
		'''
			Méthode qui retourne toutes les transisions qui 
			quittent state
		'''
		
		return set([tr for tr in self.transitions if tr.state_from is state])
	
	def solve_epsilons(self, tr):
		'''
			Retourne tous les états joints à une série d'epsilon transitions
		'''

		states_to_travel = set((tr.state_to,))
		states_travelled = set()
		
		while states_to_travel:
			# On récupère un état que l'on a pas encore traité
			state = states_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 à parcourir.
			states_to_travel |= set([tr.state_to for tr in tr_to_travel]) - states_travelled
						
			# Enfin, on ajout l'état que l'on vient de parcourir dans
			# la liste des états parcouru.
			states_travelled.add(state)
			
		return states_travelled
			
	
	def acceptance(self, word):
		states = self.initial_states
		
		for f in word:
			next_states = set()
			for s in states:
				for tr in self.leave(s):
					if type(tr) == Transition and f in tr.labels:
						next_states.add(tr.state_to)
						for etr in [t for t in self.leave(tr.state_to) if type(t) is EpsilonTransition]:
							next_states |= self.solve_epsilons(etr)
						
			states = next_states
			
		# En Python, & est l'opérateur d'intersection des ensembles
		return bool(states & self.final_states)
				
	def render(self, filename):
		'''
			Générer une image de l'automate
		'''
		
		try:
			import pygraphviz as gv
		except ImportError:
			print 'Il faut installer pygraphviz pour utiliser les méthodes de'
			print 'visualisation de l\'automate : easy_install pygraphviz'
		else:
			graph = gv.AGraph(directed=True) # Un automate est un graphe dirigé
			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)
			)

Automate.lisp