Edition, visualisation, traversal

Boolean automata

In [1]:
# We disable autosave for technical reasons.
# Replace 0 by 120 in next line to restore default.
%autosave 0

Autosave disabled
In [2]:
import awalipy # If import fails, check that 
               # Python version used as Jupyter
               # kernel matches the one
               # Awalipy was compiled with.

[Warning] The python module awalipy relies on compilation executed "on-the-fly" depending on the context (type of weights, of labels, etc.). As a result, the very first call to a given function in a given context may take up to 10 seconds.

(The above warning is displayed every time awalipy is imported.)

Creating an automaton

Alphabets we use are Python str

  • each char of the str is a letter the alphabet
  • order does not matter ("abc" and "bac" represent the same alphabet)
In [3]:
alph1 = "abc"  # represents {a,b,c}
alph2 = "01"   # represents {0,1}

An automaton is built from an alphabet

In [4]:
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.

In [5]:
stt_0 = A.add_state()
stt_1 = A.add_state()

Adding transitions

In [6]:
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')

There is no Python class for transitions or states. We manipulate only their identifiers.

In [7]:
print (stt_0)
print (tr_2)

0
2

Making states initial or final

In [8]:
A.set_initial(stt_0)
A.set_final(stt_1)

Displaying an automaton

Displaying an automaton graphically, using dot for state placement.
(Works well for small automata only.)

In [9]:
A.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 3->F3 3->2 b

Displayin an automaton in text format.

In [10]:
A
Out[10]:
Automaton (lal_char_b):	Weight Set: B	Alphabet: abc
States:{	0(i)	1(f)	}
Transitions:{	0--a-->1	1--b-->0	0--b-->0		}

NB: the mention (i) following a state means that the state is initial. Similarly, (f) means final and (i,f) means initial and final.

Epsilon transitions

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.

In [11]:
Ae = A.allow_eps_transition()
Ae.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 3->F3 3->2 b

Adding an epsilon transition using the specific function.

In [12]:
tr_3 = Ae.set_eps_transition(stt_1,stt_0)
Ae.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 3->F3 3->2 \e, b

Epsilon transition is represented by the string "\e".

(NB: the '\' must be escaped by a preceding '\')

Adding an epsilon-transition using the general function.

In [13]:
Ae.set_transition(stt_1,stt_1,"\\e")
Out[13]:
6

For convenience we also allow "" as input to mean epsilon.

In [14]:
Ae.set_transition(stt_0,stt_0,"")
Out[14]:
7

Resulting automaton:

In [15]:
Ae.display()
%3 I2 2 s0 I2->2 F3 2->2 \e, b 3 s1 2->3 a 3->F3 3->2 \e, b 3->3 \e

Deleting edges and states

Let us consider the automaton A.

In [16]:
A.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 3->F3 3->2 b

First we add a bunch of states and transitions

In [17]:
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()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 4 s2 2->4 a 3->F3 3->2 b 3->3 a 3->4 a, b 4->2 b 4->3 a 4->4 b

Deleting a transition by id

In [18]:
A.del_transition(tr_3) # tr_3 is the transition: s2 --a--> s2
A.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 4 s2 2->4 a 3->F3 3->2 b 3->4 a, b 4->2 b 4->3 a 4->4 b

Deleting a transition by triplet (origin, destination, label)

In [19]:
A.del_transition(stt_2,stt_2,'b')
A.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 4 s2 2->4 a 3->F3 3->2 b 3->4 a, b 4->2 b 4->3 a

Deleting all transitions from a state to another (order matters).

In [20]:
A.del_transition(stt_1,stt_2)
A.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 4 s2 2->4 a 3->F3 3->2 b 4->2 b 4->3 a

Deleting a state (and all its outgoing and incoming transitions)

In [21]:
A.del_state(stt_2)
A.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 3->F3 3->2 b

Loading & saving automata

Saving an automaton to file. The format used is JavaScript Object Notation (JSON) hence the extension ".json" .

In [22]:
A.save("fibo.json")
In [23]:
ls

awalipy.cpython-35m-x86_64-linux-gnu.so@  Edition1.ipynb
awalipy_purepython_extra.py@              Edition2.ipynb
awalipy_purepython_extra.pyc              Edition3.ipynb
awalipy.so@                               fibo.json
ClassicalTransformations1.ipynb           fibo_LR_additioner.json
ClassicalTransformations2.ipynb           __pycache__/
CMakeLists.txt                            RationalExpression.ipynb

Loading an automaton.

In [24]:
B = awalipy.load("fibo.json")
B.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 3->F3 3->2 b

A few example are given as part of the library. They may be listed as follows.

In [25]:
awalipy.list_example_automata()

Name              Description
----              -----------
a1 .............. NFA which recognizes words with factor 'ab'
b1 .............. Z-FA which counts the number of 'b'
binary .......... Z-FA which converts binary sequences into values
c1 .............. Z-FA that converts binary sequences on alphabet {a,b} into values
d1 .............. Z-FA which computes the difference between the numbers of 'a' and 'b'
e1 .............. Q-automaton that converts words of {a,b}^* into their binary values 'after the radix point'
evena ........... NFA which recognizes words with an even number of 'a'
fibotdc-lr ...... Sequential transducer which tries to replace 'abb' by 'baa'
gray ............ Gray code increment
heapmodel ....... Z-max-plus automaton, heap model with 2 pieces
lamplighter ..... Sequential transducer...
minab ........... Z-min-plus-automaton which computes the minimum among the numbers of 'a' and 'b' in every word
minblocka ....... Z-min-plus-automaton which computes the length of the shortest block of 'a' in every word
oddb ............ NFA which recognizes the words with an odd number of 'b'
prob-rabin ...... R-automaton (probabilistic automaton) that accepts w with prob. expansion(w)
rotation ........ C-automaton realizing a rotation
slowcerny ....... Synchronisable NFA which meets Cerny bound
slowgrow ........ Z-min-plus-automaton with a slow growing length function

Loading an example automaton (given with the library).

In [26]:
C = awalipy.load("a1")
C.display()
%3 I2 2 s0 I2->2 F4 2->2 a, b 3 s1 2->3 a 4 s2 3->4 b 4->F4 4->4 a, b

A few factories

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.

In [27]:
awalipy.make_cerny(5).display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 b 3 s1 2->3 a 3->3 b 4 s2 3->4 a 4->4 b 5 s3 4->5 a 5->5 b 6 s4 5->6 a 6->2 a, b

make_divkbaseb(k,b) returns an automaton accepting integers divisible by k, written in base b.

In [28]:
awalipy.make_divkbaseb(3,2).display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 0 3 s1 2->3 1 3->2 1 4 s2 3->4 0 4->3 0 4->4 1

make_ladybird(n) returns an automaton with n-states, whose equivalent minimal DFA has 2**n states.

In [29]:
awalipy.make_ladybird(5).display()
%3 I2 2 s0 I2->2 F2 2->F2 3 s1 2->3 a 3->2 c 3->3 b, c 4 s2 3->4 a 4->2 c 4->4 b, c 5 s3 4->5 a 5->2 c 5->5 b, c 6 s4 5->6 a 6->2 a, c 6->6 b, c

See also make_de_bruijn , make_double_ring , make_witness

Generate a random accessible DFA

In [30]:
awalipy.generate_DFA(5,"ab").display()
%3 I2 2 s0 I2->2 F2 F4 F5 F6 2->F2 3 s1 2->3 a 4 s2 2->4 b 3->3 b 5 s3 3->5 a 4->F4 4->5 b 6 s4 4->6 a 5->F5 5->2 b 5->4 a 6->F6 6->5 a, b

Access and browsing

In [31]:
A.display()
%3 I2 2 s0 I2->2 F3 2->2 b 3 s1 2->3 a 3->F3 3->2 b

Getting the list of states, of transitions.

(It cannot be assumed that the ids of states are [0,1,...,n] for some n)

In [32]:
A.states(), A.transitions()
Out[32]:
([0, 1], [0, 1, 2])

Getting the list of initial states, of final states.

In [33]:
A.initial_states(), A.final_states()
Out[33]:
([0], [1])

Listing the transitions adjacent to a state.

In [34]:
A.outgoing(stt_1), A.incoming(stt_1)
Out[34]:
([1], [0])

Listing the transitions from a state to another.

In [35]:
A.outin(stt_0,stt_1)
Out[35]:
[0]

Getting information from a transition identifier.

In [36]:
# 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.)

1
b
0
(1, 'b', '1', 0)

List of states reachable from a state in one transition.

In [37]:
A.successors(stt_0), A.successors(stt_0, 'a')
Out[37]:
([1, 0], [1])

List of states that may reach a state in one transition.

In [38]:
A.predecessors(stt_0), A.predecessors(stt_0, 'a')
Out[38]:
([1, 0], [])

Exercice: breadth-first traversal of A

In [39]:
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))
In [40]:
bf_traversal(A)

(0, 'a', '1', 1)
(0, 'b', '1', 0)
(1, 'b', '1', 0)
In [41]:
bf_traversal(awalipy.make_ladybird(3))

(0, 'a', '1', 1)
(1, 'b', '1', 1)
(1, 'c', '1', 1)
(1, 'c', '1', 0)
(1, 'a', '1', 2)
(2, 'b', '1', 2)
(2, 'c', '1', 2)
(2, 'c', '1', 0)
(2, 'a', '1', 0)
In [ ]:
In [ ]:
In [ ]: