""" This is the "automaton" module. This module offers a simple automaton class. This module is not optimized and is designed for educational purposes. """ # Copyright (C) 2013 Adrien Boussicault, University of Bordeaux 1, France # # This Library is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # # This Library is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this Library. If not, see . import subprocess import tempfile import copy import os import platform import threading import xml.etree.ElementTree as ET class pretty_set(frozenset): """ This class implements a frozen set with pretty printing function. """ def __repr__(self): elems = list(self) if len(elems) == 0 : return "{}" result = "{" + str(elems[0]) for e in elems[1:]: result += ", " + str(e) result += "}" return result def _translate( obj, nb ): """ This function translates recursively all the numbers contained in a iterable object. Keyword arguments: obj -- the object to translate nb -- the translation number Example: >>> _translate( 3, 7 ) 10 >>> _translate( (2,4), 5 ) (7, 9) >>> _translate( [(1,2),[3,(4,5),set([6,7])]], 3 ) == [(4, 5), [6, (7, 8), set([9, 10])]] True >>> type( _translate( pretty_set([1,3,5]), 3 ) ) >>> _translate( pretty_set([1,3,5]), 3 ) == pretty_set([4,6,8]) True """ def _tran( l ): if type(l) == int: return l+nb if type(l) == str: return l return type(l)(map( _tran, l )) return _tran( obj ) def _extract_maximal_id( obj ): """ This function extracts recursively the maximal integer contained inside an iterable object. Example: >>> _extract_maximal_id( 3 ) 3 >>> _extract_maximal_id( (2,4) ) 4 >>> _extract_maximal_id( [(1,2),[3,(4,5),set([6,7])]] ) 7 >>> class A: ... pass >>> _extract_maximal_id( A() ) >>> _extract_maximal_id(( pretty_set([1,(9,1),5]) )) 9 """ if type(obj) == int: return obj try: maximum = None for i in obj: val = _extract_maximal_id(i) if maximum == None : maximum = val elif val > maximum: maximum = val return maximum except: return None def _extract_minimal_id( obj ): """ This function extracts recursively the minimal integer contained inside an iterable object. Example: >>> _extract_minimal_id( 3 ) 3 >>> _extract_minimal_id( (2,4) ) 2 >>> _extract_minimal_id( [(1,2),[3,(4,5),set([6,7])]] ) 1 >>> class A: ... pass >>> _extract_minimal_id( A() ) >>> _extract_minimal_id(( pretty_set([1,(9,1),5]) )) 1 """ if type(obj) == int: return obj try: minimum = None for i in obj: val = _extract_minimal_id(i) if minimum == None : minimum = val elif val < minimum: minimum = val return minimum except: return None class _object_to_id: """ This class is used to map objects to integers going for 1 to n. Example: >>> a = _object_to_id( ) >>> a.add_object( (1,1) ) >>> a.add_object( (1,2) ) >>> a.add_object( (1,3) ) >>> a.id( (1,3) ) 3 """ def __init__( self ): self._map = {} self._nb = 1 def add_object( self, obj ): if not obj in self._map: self._map[ obj ] = self._nb self._nb += 1 def id( self, obj ): if not obj in self._map: return None return self._map[ obj ] def _test_is_hashable( obj, name ): try: pretty_set( [obj] ) except: msg = "In automaton module, " + name + " have to be hashable." if type( obj ) is set: msg += " Use automaton.pretty_set or frozenset instead of set." if type( obj ) is list: msg += " Use tuple instead of list. For example (1,3) instead of [1,3]." raise Exception( msg ) class automaton: """ This class implements an automaton without epsilon transition This automaton is defined by the 6-uple where A is an alphabet; E is a subset of A containing all the epsilon transitions Q is the set of states; I is a subset of Q and is the set of initial states; F is a subset of Q and is the set of final states; T is a subset of Q X A X Q, and is the set of transitions. """ def __init__( self, alphabet=None, epsilons=None, states=None, initials=None, finals=None, transitions=None ): """ The constructor of the automaton class During the construction, if a state (resp. a character) doesn't exist, the state (resp. character) is automatically added in the list of states (resp. alphabet). Keyword arguments: alphabet -- the alphabet [default=None] this argument has to contain a set of hashable objects epsilon characters -- the list of epsilon characters [default=None] this argument has to contain a list of hashable objects states -- the list of states [default=None] this argument has to contain a list of hashable objects initals -- the list of initial states [default = None] this argument has to contain a list of hashable objects finals -- the list of final states [default = None] this argument has to contain a list of hashable objects transitions -- the list of transitions. [default = None] a transition has to be encoded by a tuple (q1, c, q2) where q1 and q2 are states and c is a character. Example: >>> a = automaton( ... alphabet = ['d'], states = [4], ... initials = [0,2], finals = [1,3], ... transitions = [ (0,'a',0), (0,'b',1), (1,'c',1) ] ... ) >>> a.get_alphabet() == set(['a', 'b', 'c', 'd']) True >>> a.get_states() == set( [0,1,2,3,4] ) True >>> a.get_initial_states() == set( [0,2] ) True >>> a.get_final_states() == set( [1,3] ) True >>> a.get_transitions() == set( [(0,'a',0), (0,'b',1), (1,'c',1)] ) True >>> b = automaton( ... transitions = [ ... ( (1,2), 'a', (1,3) ), ... ( (1,2), 'b', (4,5) ), ... ( (4,5), 'a', (1,3) ) ... ] ... ) >>> b.get_states() == set( [(1,2), (4,5), (1,3)] ) True """ self._epsilons = set() self._states = set( ) self._adjacence = {} self._initial_states = set( ) self._final_states = set( ) self._alphabet = set( ) if alphabet != None: self.add_characters( alphabet ) if epsilons != None : self.add_epsilon_characters( epsilons ) if states != None: self.add_states( states ) if transitions != None: self.add_transitions( transitions ) if initials != None: self.add_initial_states( initials ) if finals != None: self.add_final_states( finals ) def get_maximal_id( self ): """ Returns the maximal integer present among all the states Example: >>> b = automaton( ... transitions = [ ... ( (pretty_set([-1,11]), 2), 'a', (1,9) ), ... ( (pretty_set([-1,11]), 2), 'b', (4,5) ), ... ( (4,5), 'a', (1,9) ) ... ] ... ) >>> b.get_maximal_id() 11 """ return _extract_maximal_id(self._states) def get_minimal_id( self ): """ Returns the minimal integer present among all the states Example: >>> b = automaton( ... transitions = [ ... ( (pretty_set([-1,11]), 2), 'a', (1,9) ), ... ( (pretty_set([-1,11]), 2), 'b', (4,5) ), ... ( (4,5), 'a', (1,9) ) ... ] ... ) >>> b.get_minimal_id() -1 """ return _extract_minimal_id(self._states) def has_epsilon_characters( self ): """ Returns True if automaton has epsilon character. Example: >>> automaton().has_epsilon_characters() False >>> automaton( epsilons=['0'] ).has_epsilon_characters() True """ return len( self._epsilons ) > 0 def get_epsilons( self ): """ Returns the set of epsilon characters Example: >>> automaton().get_epsilons() {} """ return pretty_set( self._epsilons ) def translate( self, nb ): """ Recursively translates all integers present in the states by ``nb`` Example: >>> b = automaton( ... transitions = [ ... ( (pretty_set([-1,11]), 2), 'a', (1,'a') ), ... ( (pretty_set([-1,11]), 2), 'b', (4,5) ), ... ( (4,5), 'a', (1,'a') ) ... ] ... ) >>> b.translate( 3 ) >>> b.get_states() == set( [ ... (pretty_set([2,14]), 5), ... (4,'a'), ... (7,8) ... ] ) True """ self._states = _translate( self._states, nb ) tmp = {} for e in self._adjacence: tmp[ _translate(e,nb) ] = _translate( self._adjacence[e], nb ) self._adjacence = tmp self._final_states = _translate( self._final_states, nb ) self._initial_states = _translate( self._initial_states, nb ) def map( self, f ): """ For each state s, this function subtitutes s by f(s) in the automaton. Keyword arguments: f -- a map from the set of states to itself. Example: >>> def parity( obj ): ... return obj%2 >>> a = automaton( ... initials = [3], finals=[4], transitions = [ ... (0,'a',1), (0,'b',1), (1,'a',2), (2,'a',3), (4,'c',3) ... ] ... ) >>> a.map( parity ) >>> a == automaton( ... initials=[1], finals=[0], transitions=[ ... (0,'a',1), (0,'b',1), (1,'a',0), (0,'c',1) ... ] ... ) True """ def _f( state ): _test_is_hashable( state, "The images of f" ) return f( state ) self._states = set( map( _f, self._states ) ) tmp = {} for e in self._adjacence: origin = _f( e[0] ) tmp[ (origin, e[1]) ] = set( map( _f,self._adjacence[e] ) ) self._adjacence = tmp self._final_states = set( map( _f, self._final_states ) ) self._initial_states = set( map( _f, self._initial_states ) ) def __eq__( self, a ): """ Tests whether two automata are equals. More precisely, that function test if the 6-uplet of the two automata are equals. Example: >>> a = automaton( ... alphabet = ['c'], epsilons = ['0'], ... states = [5], initials = [0,1], finals = [3,4], ... transitions=[ ... (0,'a',1), (1,'b',2), (2,'b',2), (2,'a',3), (3,'a',4) ... ] ... ) >>> b = a.clone() >>> a == b True >>> c = automaton( ... alphabet = ['c'], epsilons = ['0'], ... states = [5], initials = [0,1], finals = [3,4], ... transitions=[ ... (0,'a',1), (1,'b',2), (2,'b',2), (2,'a',3), (3,'a',4) ... ] ... ) >>> a == c True >>> d = automaton( ... epsilons = ['0'], ... states = [5], initials = [0,1], finals = [3,4], ... transitions=[ ... (0,'a',1), (1,'b',2), (2,'b',2), (2,'a',3), (3,'a',4) ... ] ... ) >>> a == d False """ return ( self.get_alphabet() == a.get_alphabet() and self.get_epsilons() == a.get_epsilons() and self.get_states() == a.get_states() and self.get_initial_states() == a.get_initial_states() and self.get_final_states() == a.get_final_states() and self.get_transitions() == a.get_transitions() ) def clone( self ): """ Returns a deep copy of the automaton. Example: >>> a = automaton( transitions = [ (0,'a',0), (0,'a',1) ] ) >>> b = a.clone() >>> b is a False >>> b == a True """ return copy.deepcopy( self ) def get_renumbered_automaton( self ): """ Returns a copy of the automaton with a new numbering for the states: now the states of the copy are integer going from 1 to n (n is the number of states of the automaton). Example: >>> a = automaton( ... transitions = [ ... ( (1,2), 'a', (1,3) ), ... ( (1,2), 'b', (4,5) ), ... ( (4,5), 'a', (1,3) ) ... ] ... ) >>> b = a.get_renumbered_automaton() >>> a is b False >>> b.get_states() == set( [1,2,3] ) True """ result = self.clone() result.renumber_the_states() return result def renumber_the_states( self ): """ Renumbers all states of the automaton from 1 to n, where n is the number of automaton states. Example: >>> b = automaton( ... transitions = [ ... ( (1,2), 'a', (1,3) ), ... ( (1,2), 'b', (4,5) ), ... ( (4,5), 'a', (1,3) ) ... ] ... ) >>> b.renumber_the_states() >>> b.get_states() == set( [1,2,3] ) True """ state_to_id = _object_to_id() for state in self._states: state_to_id.add_object( state ) states = set() for state in self._states: states.add( state_to_id.id( state ) ) initials = set() for state in self._initial_states: initials.add( state_to_id.id( state ) ) finals = set() for state in self._final_states: finals.add( state_to_id.id( state ) ) transitions = {} def renum( obj ): return state_to_id.id(obj) for o in self._adjacence: transitions[ ( state_to_id.id(o[0]), o[1]) ] = set( map( renum, self._adjacence[o] ) ) self._initial_states = initials self._states = states self._final_states = finals self._adjacence = transitions def add_initial_state( self, state ): """ Adds an initial state Example: >>> a = automaton( ) >>> a.get_states() == set() True >>> a.add_initial_state( 2 ) >>> a.get_states() == set( [2] ) True >>> a.get_initial_states() == set( [2] ) True """ self.add_state( state ) self._initial_states.add( state ) def add_initial_states( self, list_of_states ): """ Adds a list of initial states Example: >>> a = automaton( ) >>> a.get_states() == set() and a.get_initial_states() == set() True >>> a.add_initial_states( [ 1,2,3 ] ) >>> a.get_states() == set( [1,2,3] ) True >>> a.get_initial_states() == set( [1,2,3] ) True """ for state in list_of_states: self.add_initial_state( state ) def add_final_state( self, state ): """ Adds a final state Example: >>> a = automaton( ) >>> a.get_states() == set() True >>> a.add_final_state( 2 ) >>> a.get_states() == set( [2] ) True >>> a.get_final_states() == set( [2] ) True """ self.add_state( state ) self._final_states.add( state ) def add_final_states( self, list_of_states ): """ Adds a list of final states Example: >>> a = automaton( ) >>> a.get_states() == set() and a.get_final_states() == set() True >>> a.add_final_states( [ 1,2,3 ] ) >>> a.get_states() == set( [1,2,3] ) True >>> a.get_final_states() == set( [1,2,3] ) True """ for state in list_of_states: self.add_final_state( state ) def add_state( self, state ): """ Adds a state. The state have to be hashable. That's why you have to use: automaton.pretty_set or frozenset instead of set tuple instead of list Example: >>> a = automaton( ) >>> a.get_states() == set() True >>> a.add_state( 2 ) >>> a.get_states() == set( [2] ) True >>> a.add_state( (1,3) ) >>> a.get_states() == set( [2, (1,3)] ) True We get an error if we try to use a set to code a state: >>> a.add_state( set([1,2,5]) ) Traceback (most recent call last): ... Exception: In automaton module, States have to be hashable. Use automaton.pretty_set or frozenset instead of set. The solution is to use automaton.pretty_set: >>> a.add_state( pretty_set([1,2,5]) ) We get an error if we try to use a list to code a state: >>> a.add_state( [1,2,5] ) Traceback (most recent call last): ... Exception: In automaton module, States have to be hashable. Use tuple instead of list. For example (1,3) instead of [1,3]. The solution is to use a tuple: >>> a.add_state( (1,2,5) ) """ _test_is_hashable( state, "States" ) self._states.add( state ) def add_states( self, list_of_states ): """ Adds a list of states. Example: >>> a = automaton( ) >>> a.add_states( [1,2,6] ) >>> a.get_states() == set( [1,2,6] ) True """ for state in list_of_states: self.add_state( state ) def add_character( self, character ): """ Adds a character in the alphabet of the automaton. Characters have to be hashable. That's why you have to use: automaton.pretty_set or frozenset instead of set tuple instead of list Example: >>> a = automaton( ) >>> a.add_character( 'a' ) >>> a.get_alphabet() == set( ['a'] ) True We get an error if we try to use a set to code a character: >>> a.add_character( set([1,2,5]) ) Traceback (most recent call last): ... Exception: In automaton module, Characters have to be hashable. Use automaton.pretty_set or frozenset instead of set. The solution is to use automaton.pretty_set: >>> a.add_character( pretty_set([1,2,5]) ) We get an error if we try to use a list to code a character: >>> a.add_character( [1,2,5] ) Traceback (most recent call last): ... Exception: In automaton module, Characters have to be hashable. Use tuple instead of list. For example (1,3) instead of [1,3]. The solution is to use a tuple: >>> a.add_character( (1,2,5) ) """ _test_is_hashable( character, "Characters" ) self._alphabet.add( character ) def add_characters( self, list_of_characters ): """ Adds all the characters of a list in the alphabet of the automaton. Example: >>> a = automaton( ) >>> a.add_characters( ['a','b'] ) >>> a.get_alphabet() == set( ['a','b'] ) True """ for character in list_of_characters: self.add_character( character ) def add_epsilon_character( self, character ): """ Defines an epsilon character and adds that character in the alphabet. Characters have to be hashable. That's why you have to use: automaton.pretty_set or frozenset instead of set tuple instead of list Example: >>> a = automaton( ) >>> a.add_epsilon_character( '0' ) >>> a.get_epsilons() == set( ['0'] ) True We get an error if we try to use a set to code an epsilon character: >>> a.add_epsilon_character( set([1,2,5]) ) Traceback (most recent call last): ... Exception: In automaton module, Epsilon characters have to be hashable. Use automaton.pretty_set or frozenset instead of set. The solution is to use automaton.pretty_set: >>> a.add_epsilon_character( pretty_set([1,2,5]) ) We get an error if we try to use a list to code an epsilon character: >>> a.add_epsilon_character( [1,2,5] ) Traceback (most recent call last): ... Exception: In automaton module, Epsilon characters have to be hashable. Use tuple instead of list. For example (1,3) instead of [1,3]. The solution is to use a tuple: >>> a.add_epsilon_character( (1,2,5) ) """ _test_is_hashable( character, "Epsilon characters" ) self.add_character( character ) self._epsilons.add( character ) def add_epsilon_characters( self, list_of_characters ): """ Defines all the characters of a list as epsilon characters. Example: >>> a = automaton( ) >>> a.add_epsilon_characters( ['a','b'] ) >>> a.get_epsilons() == set( ['a','b'] ) True """ for character in list_of_characters: self.add_epsilon_character( character ) def add_transition( self, transition ): """ Adds a transition. The transition has to be a tuple (q1, c, q2) where q1 and q2 are states, and c is a character. Example: >>> a = automaton() >>> a.add_transition( (1,'a',2) ) >>> a.get_transitions() == set( [ (1,'a',2) ] ) True """ _test_is_hashable( transition, "Transition" ) ( q1, lettre, q2 ) = transition self.add_state( q1 ) self.add_state( q2 ) self.add_character( lettre ) if( not (q1,lettre) in self._adjacence ): self._adjacence[ (q1, lettre) ] = set( ) self._adjacence[ (q1, lettre) ].add( q2 ) def add_transitions( self, list_of_transitions ): """ Adds a list of transitions. The transitions have to be a tuple (q1, c, q2) where q1 and q2 are states, and c is a character. Example: >>> a = automaton() >>> a.add_transitions( [ (1,'a',2), (1,'b',1) ] ) >>> a.get_transitions() == set( [ (1,'a',2), (1,'b',1) ] ) True """ for transition in list_of_transitions: self.add_transition( transition ) def has_character( self, character ): """ Tests whether a character is in the alphabet. Example: >>> a = automaton( alphabet=['a','b']) >>> a.has_character( 'a' ) and a.has_character( 'b' ) True >>> a.has_character( 'c' ) False """ return character in self._alphabet def has_state( self, state ): """ Tests whether a state is in the automaton. Example: >>> a = automaton( states=[1, (1,2)] ) >>> a.has_state( 1 ) and a.has_state( (1,2) ) True >>> a.has_state( 2 ) False """ return state in self._states def state_is_initial( self, state ): """ Tests whether a state is initial. Example: >>> a = automaton( states= [1,2,3,4], initials=[1, 3] ) >>> a.state_is_initial( 1 ) and a.state_is_initial( 3 ) True >>> not( a.state_is_initial( 2 ) ) and not( a.state_is_initial( 4 ) ) True """ return state in self._initial_states def get_states( self ): """ Returns the list of states. Example: >>> a = automaton( states= [1,2,3,4] ) >>> a.get_states() == set( [1,2,3,4] ) True """ return pretty_set(self._states) def get_transitions( self ): """ Returns the list of transitions. Example: >>> a = automaton( transitions= [ (0,'a',1), (1,'b',1), (1,'a',0) ] ) >>> a.get_transitions() == set( [ (0,'a',1), (1,'b',1), (1,'a',0) ] ) True """ transitions = set() for key in self._adjacence: for end in self._adjacence[key]: transitions.add( (key[0], key[1], end) ) return pretty_set(transitions) def state_is_final( self, state ): """ Tests whether a state is final. Example: >>> a = automaton( states= [1,2,3,4], finals=[1, 3] ) >>> a.state_is_final( 1 ) and a.state_is_final( 3 ) True >>> not( a.state_is_final( 2 ) ) and not( a.state_is_initial( 4 ) ) True """ return state in self._final_states def get_initial_states( self ): """ Returns the list of initial states. Example: >>> a = automaton( states=[1,2,3,4], initials=[ 1,3 ] ) >>> a.get_initial_states() == set( [ 1, 3 ] ) True """ return pretty_set(self._initial_states) def get_final_states( self ): """ Returns the list of final states. Example: >>> a = automaton( states=[1,2,3,4], finals=[ 1,3 ] ) >>> a.get_final_states() == set( [ 1, 3 ] ) True """ return pretty_set(self._final_states) def get_alphabet( self ): """ Returns the alphabet. Example: >>> a = automaton( alphabet=['a','c'] ) >>> a.get_alphabet() == set( [ 'a', 'c' ] ) True """ return pretty_set(self._alphabet) def _delta( self, character, states ): result = set() for state in states: if (state,character) in self._adjacence: result.update( self._adjacence[ (state,character) ] ) return pretty_set( result ) def _expand_epsilons( self, states): old = pretty_set( ) result = pretty_set( states ) while( old != result ): old = result for eps in self._epsilons: result = result.union( self._delta( eps, result ) ) return pretty_set(result) def remove_epsilon_transitions( self ): """ Removes all the epsilon transition Example: >>> a = automaton( epsilons=['0','1']) >>> a.get_alphabet() == set( ['0','1'] ) and a.get_epsilons() == set( ['0','1'] ) True >>> a.remove_epsilon_transitions() >>> a.get_alphabet() == set( ['0','1'] ) and a.get_epsilons() == set( ) True """ self._epsilons = set() def delta( self, character, states=None, ignore_epsilons=False ): """ Returns the accessible states from some states by reading a character. Let ``states`` be the input set of state. Let``character`` be the input character. if ``character`` is an epsilon character, then the output is all the states connected with ``states`` by using a path of epsilon transitions. if ``character`` is not an epsilon character, The output is the set of vertices connected to ``state`` by using a path containing exactly one transition labeled by ``character`` and any number of epsilon transitions. Keyword Arguments: states -- A set of states [default= the inital states of the automaton] character -- a character ignore_epsilons -- if set to True, all the epsilon charaters will be considerated as usal character ( The input character will be considerated as usual character ) Example: An exemple without epsilon transitions: >>> a = automaton( ... initials=[0], finals=[1], ... transitions=[ ... (0,'a',1), (0,'a',2),(1,'b',2),(2,'a',1) ... ] ... ) >>> a.delta( 'a' ) == a.delta( 'a', a.get_initial_states() ) True >>> a.delta( 'a' ) == set( [1,2] ) True >>> a.delta( 'b' ) == set( ) True >>> a.delta( 'a', [2] ) == set( [1] ) True >>> a.delta( 'a', [1,2] ) == set( [1] ) True An exemple with epsilon transitions: >>> a = automaton( ... epsilons=['0'], ... initials=[0], finals=[3], ... transitions=[ ... (0,'0',1), (1,'a',2), (1,'b',3), (2,'0',3), (3,'b',2), ... (3,'a',0) ... ] ... ) >>> a.delta( 'a' ) == a.delta( 'a', a.get_initial_states() ) True >>> a.delta( 'a' ) == set( [2,3] ) True >>> a.delta( 'b' ) == set( [3] ) True >>> a.delta( '0' ) == set( [0,1] ) True >>> a.delta( 'a', [1,2] ) == set( [0,1,2,3] ) True >>> a.delta( 'b', [1,2] ) == set( [2,3] ) True >>> a.delta( '0', [1,2] ) == set( [1,2,3] ) True If we want to ignore the epsilon transitions: >>> a.delta( 'a', ignore_epsilons=True ) == set() True >>> a.delta( 'b', ignore_epsilons=True ) == set() True >>> a.delta( '0', ignore_epsilons=True ) == set( [1] ) True >>> a.delta( 'a', [1,2], True ) == set( [2] ) True >>> a.delta( 'b', [1,2], True ) == set( [3] ) True >>> a.delta( '0', [1,2], True ) == set( [3] ) True """ if states==None: states = self.get_initial_states() if( ignore_epsilons or not( self.has_epsilon_characters() ) ): return self._delta( character, states ) else: result = self._expand_epsilons( states ) if( character in self._epsilons ): return result result = self._delta( character, result ) return self._expand_epsilons( result ) def delta_star( self, word, states=None, ignore_epsilons=False ): """ if len(word)>0 return delta_star( word[1:], delta( word[0], states ) ) else return the set of epsilon accessible states from the input states ``states``. Keyword Arguments: states -- A set of states [default= the inital states of the automaton] character -- a character ignore_epsilons -- if set to True, all the epsilon charaters will be considerated as usal characters ( the input characters will be considated as usual characters ) Example: >>> a = automaton( ... initials=[0], finals=[1], ... transitions=[ ... (0,'a',1), (0,'a',2),(1,'b',2),(2,'a',1) ... ] ... ) >>> a.delta_star( [ 'a', 'b', 'a' ] ) == set( [1] ) True >>> a.delta_star( [ 'b', 'a' ] ) == set( ) True >>> a.delta_star( [ ] ) == set( [0] ) True >>> a.delta_star( [ 'a', 'b', 'a' ], [1] ) == set() True >>> a.delta_star( [ 'b', 'a' ], [0,1] ) == set( [1] ) True >>> a.delta_star( [], [1] ) == set( [1] ) True An exemple with epsilon transitions: >>> a = automaton( ... epsilons=['0'], ... initials=[0], finals=[3], ... transitions=[ ... (0,'0',1), (1,'a',2), (1,'b',3), (2,'0',3), (3,'b',2), ... (3,'a',0) ... ] ... ) >>> a.delta_star( [ 'b', 'a', 'a' ] ) == set( [2,3] ) True >>> a.delta_star( [ '0', 'b', '0', 'a', '0' ] ) == a.delta_star( [ 'b', 'a' ] ) True >>> a.delta_star( [ 'b', '0', 'a' ] ) == set( [0,1] ) True If we want to ignore the epsilon transitions: >>> a.delta_star( [ 'b', 'a', 'a' ], ignore_epsilons=True ) == set() True >>> a.delta_star( [ '0', 'b', 'a', '0', 'a' ], ignore_epsilons=True ) == set( [2] ) True >>> a.delta_star( [ 'b', 'a' ], ignore_epsilons=True ) == set( ) True """ if states==None: states = self.get_initial_states() if( ignore_epsilons or not( self.has_epsilon_characters() ) ): result = states for character in word: result = self._delta( character, result ) return pretty_set(result) else: result = self._expand_epsilons( states ) for character in word: result = self.delta( character, result ) return pretty_set(result) def word_is_recognized( self, word, initial_states=None, ignore_epsilons=False ): """ Returns True if the word is recognized by the automaton. Epsilon characters are considerated to be the same neutral element of the free monoide of the words on the set of non-epsilon characters. Keyword arguments: world -- a list of character initial_states -- a alternative set of initial state [default=the initial set of the automaton] ignore_epsilons -- if set to True, all the epsilon charaters will be considerated as usal characters ( the characters of the input world will be considated as usual characters ) Example: An exemple without epsilon transitions: >>> a = automaton( ... initials=[0], finals=[1], ... transitions=[ ... (0,'a',1), (0,'a',2),(1,'b',2),(2,'a',1) ... ] ... ) >>> a.word_is_recognized( [ 'a', 'b', 'a' ] ) True >>> a.word_is_recognized( [ 'b', 'a' ] ) False >>> a.word_is_recognized( [ ] ) False >>> a.word_is_recognized( [ 'a', 'b', 'a' ], [1] ) False >>> a.word_is_recognized( [ 'b', 'a' ], [0,1] ) True >>> a.word_is_recognized( [ ], [1] ) True An exemple with epsilon transitions: >>> a = automaton( ... epsilons=['0'], ... initials=[0], finals=[3], ... transitions=[ ... (0,'0',1), (1,'a',2), (1,'b',3), (2,'0',3), (3,'b',2), ... (3,'a',0) ... ] ... ) >>> a.word_is_recognized( [ 'b', 'a', 'a' ] ) True >>> a.word_is_recognized( [ '0', 'b', '0', 'a', '0' ] ) == a.word_is_recognized( [ 'b', 'a' ] ) True >>> a.word_is_recognized( [ 'b', '0', 'a' ] ) False If we want to ignore the epsilon transitions: >>> a.word_is_recognized( [ 'b', 'a', 'a' ], ignore_epsilons=True ) False >>> a.word_is_recognized( [ '0', 'b', 'a', '0', 'a' ], ignore_epsilons=True ) False >>> a.word_is_recognized( [ 'b', 'a' ], ignore_epsilons=True ) False """ ending_states = self.delta_star( word, initial_states, ignore_epsilons ) for state in ending_states: if self.state_is_final( state ): return True return False def to_dot( self, title=None ): """ Returns the string containing the dot format of the automaton. Example: >>> a = automaton() >>> print( a.to_dot() ) digraph G { } """ state_to_id = _object_to_id() for state in self._states: state_to_id.add_object( state ) result = "" result += '\ndigraph G {' if( title != None ): result += '\n\t// title' result += '\n\tlabelloc="t";' result += '\n\tlabel="' + str(title) + '";' for origin in self._states: for character in self._alphabet: if( (origin,character) in self._adjacence ): for end in self._adjacence[ (origin, character) ]: result += ( '\n\t' + str(state_to_id.id(origin)) + '->' + str(state_to_id.id(end)) + ' [label=' + str(character) + ', shape=normal]' ) for state in self._states: if state in self._final_states and state in self._initial_states: result += ( '\n\t' + str(state_to_id.id(state)) + ' [margin=0.0, shape=diamond, peripheries=2, label="' + str(state) + '"];' ) elif state in self._final_states: result += ( '\n\t' + str(state_to_id.id(state)) + ' [margin=0.0, shape=oval, peripheries=2, label="' + str(state) + '"];' ) elif state in self._initial_states: result += ( '\n\t' + str(state_to_id.id(state)) + ' [margin=0.0, shape=diamond, label="' + str(state) + '"];' ) else: result += ( '\n\t' + str(state_to_id.id(state)) + ' [margin=0.0, shape=oval, label="' + str(state) + '"];' ) result += '\n}' return result def display( self, title=None, wait=True ): """ Displays the automaton on the screen. Keyword Arguments: title -- The title of the figure [default=None] wait -- If set to True, display(...) interupt the program, display the automaton and the program will continue if the user close the automaton window. Tf set to False, display(...) display the automaton, but doesn't block the execution of the main program. Bug: On Windows, display never dosen't block the execution of the main program. On Windows, temporary files are not freed. """ f=tempfile.NamedTemporaryFile(delete=False) f.write( self.to_dot( title ).encode( 'utf-8' ) ) f.close() def render_with_dotty(): process=subprocess.call( 'dotty ' + f.name, shell=True ) # A HACK if not( platform.system()=='Windows' ): os.remove(f.name) if wait : render_with_dotty() else: a = threading.Thread( target=render_with_dotty ) a.start() def xml_to_list_of_automata( xml_path ): """ Converts an xml file to a list of automata. Keyword arguments: xml_path -- the path of the xml file. Example: We create a temporary file and write in that file the xml code of two automata. Then we load that two automata with the xml_to_list_of_automata( ... ) function. >>> f=tempfile.NamedTemporaryFile() >>> f.write( ... ''' ... ... ... ... ab ... 123 ... 1 ... 23 ... ... 1a2 ... 2b3 ... ... ... ... ... 0 ... 1 ... 1 ... ... 1a2 ... 201 ... ... ... ... ... '''.encode('utf-8') ... ) != 0 True >>> f.flush() >>> [automate1, automate2] = xml_to_list_of_automata( f.name ) >>> f.close() """ tree = ET.parse(xml_path) doc = tree.getroot() result = [] for xml_automaton in doc.findall('./automaton'): aut = automaton() for xml_character in xml_automaton.findall('epsilons/c'): aut.add_epsilon_character( str(xml_character.text) ) for xml_character in xml_automaton.findall('alphabet/c'): aut.add_character( str(xml_character.text) ) for xml_state in xml_automaton.findall('states/s'): aut.add_state( int(xml_state.text) ) for xml_state in xml_automaton.findall('initials/s'): aut.add_initial_state( int(xml_state.text) ) for xml_state in xml_automaton.findall('finals/s'): aut.add_final_state( int(xml_state.text) ) for xml_transition in xml_automaton.findall('transitions/t'): aut.add_transition( ( int(xml_transition.findall('o')[0].text), str(xml_transition.findall('c')[0].text), int(xml_transition.findall('e')[0].text) ) ) result.append(aut) return result if __name__ == "__main__": import doctest doctest.testmod()