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