# We disable autosave for technical reasons.
# Replace 0 by 120 in next line to restore default.
%autosave 0
import awalipy # If import fails, check that
# Python version used as Jupyter
# kernel matches the one
# Awalipy was compiled with.
(The above warning is displayed every time awalipy is imported.)
Alphabets we use are Python str
char
of the str
is a letter the alphabet"abc"
and "bac"
represent the same alphabet)alph1 = "abc" # represents {a,b,c}
alph2 = "01" # represents {0,1}
An automaton is built from an alphabet
A = awalipy.Automaton(alph1)
# or directly `awalipy.Automaton("abc")`
A
is an automaton with no states and no transitions over the alphabet {a,b,c}
Adding states
By default the displayed name of the state is given by its index: the first state is named "s0"
, the second "s1"
, etc.
stt_0 = A.add_state()
stt_1 = A.add_state()
Adding transitions
tr_0 = A.set_transition(stt_0,stt_1,'a')
tr_1 = A.set_transition(stt_1,stt_0,'b')
tr_2 = A.set_transition(stt_0,stt_0,'b')
print (stt_0)
print (tr_2)
Making states initial or final
A.set_initial(stt_0)
A.set_final(stt_1)
Displaying an automaton graphically, using dot for state placement.
(Works well for small automata only.)
A.display()
Displayin an automaton in text format.
A
NB: the mention (i)
following a state means that the state is initial. Similarly, (f)
means final and (i,f)
means initial and final.
By default, automata do not allow epsilon transitions.
Moreover, automata with/without epsilon transitions are not represented by the same data structure. Allowing epsilon transition hence provokes a complete copy of the automaton.
Ae = A.allow_eps_transition()
Ae.display()
Adding an epsilon transition using the specific function.
tr_3 = Ae.set_eps_transition(stt_1,stt_0)
Ae.display()
Epsilon transition is represented by the string "\e"
.
(NB: the '\'
must be escaped by a preceding '\'
)
Adding an epsilon-transition using the general function.
Ae.set_transition(stt_1,stt_1,"\\e")
For convenience we also allow ""
as input to mean epsilon.
Ae.set_transition(stt_0,stt_0,"")
Resulting automaton:
Ae.display()
Let us consider the automaton A
.
A.display()
First we add a bunch of states and transitions
stt_2 = A.add_state()
tr_3 = A.set_transition(stt_1,stt_1,'a')
# Not recording ids of transitions any further
A.set_transition(stt_2,stt_2,'b')
A.set_transition(stt_0,stt_2,'a')
A.set_transition(stt_2,stt_0,'b')
A.set_transition(stt_1,stt_2,'b')
A.set_transition(stt_1,stt_2,'a')
A.set_transition(stt_2,stt_1,'a')
A.display()
Deleting a transition by id
A.del_transition(tr_3) # tr_3 is the transition: s2 --a--> s2
A.display()
Deleting a transition by triplet (origin, destination, label)
A.del_transition(stt_2,stt_2,'b')
A.display()
Deleting all transitions from a state to another (order matters).
A.del_transition(stt_1,stt_2)
A.display()
Deleting a state (and all its outgoing and incoming transitions)
A.del_state(stt_2)
A.display()
Saving an automaton to file. The format used is JavaScript Object Notation (JSON) hence the extension ".json" .
A.save("fibo.json")
ls
Loading an automaton.
B = awalipy.load("fibo.json")
B.display()
A few example are given as part of the library. The examples are listed by the following function.
examples_dict = awalipy.list_examples()
for kind in ["automata","ratexps"]:
print("======== {} ==========".format(kind))
for name in examples_dict[kind]:
print("- {}\t{}".format(name, examples_dict[kind][name]))
print ("")
Example automata can be loaded with the function load
with their name
C = awalipy.load("a1")
C.display()
make_cerny(n)
returns an n
-states DFA whose smallest synchronising word is of length (n-1)**2
. This automaton attains the upper bound for the Cerny conjecture.
awalipy.make_cerny(5).display()
make_divkbaseb(k,b)
returns an automaton accepting integers divisible by k
, written in base b
.
awalipy.make_divkbaseb(3,2).display()
make_ladybird(n)
returns an automaton with n
-states, whose equivalent minimal DFA has 2**n
states.
awalipy.make_ladybird(5).display()
See also make_de_bruijn
, make_double_ring
, make_witness
awalipy.make_random_DFA(5,"ab").display()
A.display()
Getting the list of states, of transitions.
(It cannot be assumed that the ids of states are [0,1,...,n]
for some n)
A.states(), A.transitions()
Getting the list of initial states, of final states.
A.initial_states(), A.final_states()
Listing the transitions adjacent to a state.
A.outgoing(stt_1), A.incoming(stt_1)
Listing the transitions from a state to another.
A.outin(stt_0,stt_1)
Getting information from a transition identifier.
# NB: tr_1 is a transition s1 --b--> s0
print (A.src_of(tr_1)) ## Source of transition tr_2
print (A.label_of(tr_1)) ## Label of tr_2
print (A.dst_of(tr_1)) ## Destination of tr_2
print (A.unpack_transition(tr_1)) ## All the above. (Third component
## is the weight and may be ignored.)
List of states reachable from a state in one transition.
A.successors(stt_0), A.successors(stt_0, 'a')
List of states that may reach a state in one transition.
A.predecessors(stt_0), A.predecessors(stt_0, 'a')
def bf_traversal(A):
visited = {}
for i in A.states():
visited[i] = False
to_treat = A.initial_states()
while len(to_treat) > 0 :
stt = to_treat.pop()
if not (visited[stt]):
visited[stt] = True
out_trs = A.outgoing(stt)
for tr in out_trs:
print (A.unpack_transition(tr))
to_treat.append(A.dst_of(tr))
bf_traversal(A)
bf_traversal(awalipy.make_ladybird(3))