Edition, visualisation, traversal

Boolean transducers


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. 

Creating a transducer

A Transducer is an automaton with multiple tapes. It is built from a list of alphabets.

In [3]:
T = awalipy.Transducer(["012","01"])

Adding states is the same as for automata

In [4]:
stt_0 = T.add_state()
stt_1 = T.add_state()
T.set_initial(stt_0)
T.set_final(stt_0)

Transitions of transducer bear multiple labels (in the example, two). The third argument of set_transition is now a list of labels.

In [5]:
tr_0 = T.set_transition(stt_0,stt_0,['0','0'])
tr_1 = T.set_transition(stt_0,stt_0,['1','1'])
tr_2 = T.set_transition(stt_0,stt_1,['2','0'])
tr_3 = T.set_transition(stt_1,stt_0,['0','1'])
tr_4 = T.set_transition(stt_1,stt_1,['2','1'])
tr_5 = T.set_transition(stt_1,stt_1,['1','0'])

Displaying a Transducer


Displaying a Transducer is the same as for automata.

In [6]:
T.display(True)
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1)
In [7]:
T
Out[7]:
Transducer (lat<lan<lal_char>,lan<lal_char>>_b):	Weight Set: B	Alphabets: ['012', '01']
States:{	0(i,f)	1	}
Transitions:{	0--(0,0)-->0	0--(1,1)-->0	0--(2,0)-->1	1--(0,1)-->0	1--(2,1)-->1	1--(1,0)-->1		}

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, transducers allow epsilon on any number of tapes.

In [8]:
stt_2 = T.add_state()

Adding an epsilon-transition, that is, with epsilon on all tapes.

In [9]:
tr_6 = T.set_eps_transition(stt_2,stt_1)
tr_7 = T.set_transition(stt_1,stt_2,["",""])
T.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1) 4 s2 3->4 (\e,\e) 4->3 (\e,\e)

Adding a transition with epsilon on only one tape.

In [10]:
tr_8 = T.set_transition(stt_2,stt_0,["0",""])
tr_9 = T.set_transition(stt_2,stt_2,["","1"])
T.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1) 4 s2 3->4 (\e,\e) 4->2 (0,\e) 4->3 (\e,\e) 4->4 (\e,1)

Deleting edges and states

Let us consider the automaton A

In [11]:
T.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1) 4 s2 3->4 (\e,\e) 4->2 (0,\e) 4->3 (\e,\e) 4->4 (\e,1)


Let us add a transition.

In [12]:
tr_10 = T.set_transition(stt_0,stt_2,["0","1"])
T.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 4 s2 2->4 (0,1) 3->2 (0,1) 3->3 (1,0), (2,1) 3->4 (\e,\e) 4->2 (0,\e) 4->3 (\e,\e) 4->4 (\e,1)

Deleting the transition we just added by id.

In [13]:
T.del_transition(tr_10)
T.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1) 4 s2 3->4 (\e,\e) 4->2 (0,\e) 4->3 (\e,\e) 4->4 (\e,1)

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

In [14]:
T.del_transition(stt_2,stt_2,["","1"])
T.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1) 4 s2 3->4 (\e,\e) 4->2 (0,\e) 4->3 (\e,\e)

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

In [15]:
T.del_transition(stt_2,stt_1)
T.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1) 4 s2 3->4 (\e,\e) 4->2 (0,\e)

Deleting a state (and all outgoing and incomings transitions)

In [16]:
T.del_state(stt_2)
T.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1)

Loading & saving automata

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

In [17]:
T.save("fibo_LR_additioner.json")
In [18]:
ls *json
fibo.json  fibo_LR_additioner.json

Loading an automaton.

In [19]:
B = awalipy.load("fibo_LR_additioner.json")
B.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1)

Listing the example automata given with the library. Some of them are transducers

In [20]:
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): just use the name of the automaton given above, without extension.

In [21]:
L = awalipy.load("gray")
L.display()
%3 I2 2 s0 I2->2 I3 3 s1 I3->3 F4 F6 2->2 (0,0) 2->3 (1,1) 4 s2 3->4 (0,1) 5 s3 3->5 (1,0) 6 s4 3->6 (\e,1) 4->F4 4->4 (0,0) 4->5 (1,1) 5->4 (1,1) 5->5 (0,0) 6->F6
In [22]:
s = awalipy.RatExp("0")
for i in range(20):
    print (str(i) + " is represented as " + str(s))
    s = L(s)
0 is represented as 0
1 is represented as 1
2 is represented as 11
3 is represented as 01
4 is represented as 011
5 is represented as 111
6 is represented as 101
7 is represented as 001
8 is represented as 0011
9 is represented as 1011
10 is represented as 1111
11 is represented as 0111
12 is represented as 0101
13 is represented as 1101
14 is represented as 1001
15 is represented as 0001
16 is represented as 00011
17 is represented as 10011
18 is represented as 11011
19 is represented as 01011

Access and browsing

Accessing and browsing is essentially the same for transducers and automata.

In [23]:
T.display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 (0,0), (1,1) 3 s1 2->3 (2,0) 3->2 (0,1) 3->3 (1,0), (2,1)

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

In [24]:
T.states(), T.transitions()
Out[24]:
([0, 1], [2, 3, 4, 5, 6, 7])

Getting the list of initial states,of final states.

In [25]:
T.initial_states(), T.final_states()
Out[25]:
([0], [0])

List of transitions adjacent of a state

In [26]:
T.outgoing(stt_1), T.incoming(stt_1)
Out[26]:
([5, 6, 7], [4, 6, 7])

List of transitions from a state to another.

In [27]:
T.outin(stt_0,stt_1)
Out[27]:
[4]

List of states reachable from a state in one transition.

In [28]:
T.successors(stt_0), T.successors(stt_0, ["1","0"])
Out[28]:
([0, 0, 1], [])

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

In [29]:
T.predecessors(stt_0), T.predecessors(stt_0, ["0","0"])
Out[29]:
([0, 0, 1], [0])