| |
- __builtin__.frozenset(__builtin__.object)
-
- pretty_set
- automaton
class automaton |
|
This class implements an automaton without epsilon transition
This automaton is defined by the 6-uple <A, E, Q, I, F, T> 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. |
|
Methods defined here:
- __eq__(self, a)
- Tests whether two automata are equals.
More precisely, that function test if the 6-uplet
<A, E, Q, I, F, T> 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
- __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
- 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) )
- 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
- 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) )
- 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
- 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
- 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
- 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
- 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
- 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) )
- 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
- 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
- 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
- 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
- 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
- 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
- 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.
- get_alphabet(self)
- Returns the alphabet.
Example:
>>> a = automaton( alphabet=['a','c'] )
>>> a.get_alphabet() == set( [ 'a', 'c' ] )
True
- get_epsilons(self)
- Returns the set of epsilon characters
Example:
>>> automaton().get_epsilons()
{}
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- has_epsilon_characters(self)
- Returns True if automaton has epsilon character.
Example:
>>> automaton().has_epsilon_characters()
False
>>> automaton( epsilons=['0'] ).has_epsilon_characters()
True
- 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
- 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
- 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
- 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_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
- 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
- to_dot(self, title=None)
- Returns the string containing the dot format of the automaton.
Example:
>>> a = automaton()
>>> print( a.to_dot() )
<BLANKLINE>
digraph G {
}
- 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
- 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
|
|