Classical transformations

Graphs


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. 

Strongly connected components

Let us consider an arbitrary random.
(It is probable that generate_DFA produces a strongly connected automaton, hence the sligthly convoluted code below. )

In [3]:
A = awalipy.generate_DFA(2,"ab")
B = awalipy.generate_DFA(3,"ab")
C = awalipy.generate_DFA(4,"ab")
D = A.union(B).union(C)
D.set_transition(0,2,"a")
D.set_transition(5,2,"a")
D.display()
%3 I2 2 s0 I2->2 I4 4 s2 I4->4 I7 7 s5 I7->7 F2 F4 F6 F7 F9 F10 2->F2 2->2 b 3 s1 2->3 a 2->4 a 3->3 a, b 4->F4 5 s3 4->5 a 6 s4 4->6 b 5->5 a 5->6 b 6->F6 6->6 a, b 7->F7 7->4 a 8 s6 7->8 a 9 s7 7->9 b 8->8 a 10 s8 8->10 b 9->F9 9->9 a, b 10->F10 10->7 a 10->8 b

The method sccs gives the list of the strongly connected components that is, a list of list of int.

In [4]:
D.sccs()
Out[4]:
[[4], [3], [2], [1], [0], [7], [8, 6, 5]]

The method scc_of(stt_id) gives the list of the states that may reach and may be reached from stt_id.

In [5]:
D.scc_of(4)
Out[5]:
[4]

Accessible, co-accessible, trim

In [6]:
E = D.copy()
E.display()
%3 I2 2 s0 I2->2 I4 4 s2 I4->4 I7 7 s5 I7->7 F2 F4 F6 F7 F9 F10 2->F2 2->2 b 3 s1 2->3 a 2->4 a 3->3 a, b 4->F4 5 s3 4->5 a 6 s4 4->6 b 5->5 a 5->6 b 6->F6 6->6 a, b 7->F7 7->4 a 8 s6 7->8 a 9 s7 7->9 b 8->8 a 10 s8 8->10 b 9->F9 9->9 a, b 10->F10 10->7 a 10->8 b
In [7]:
for i in [5,6,7,8] :
    E.unset_initial(i)
for i in [2,3,4] :
    E.unset_final(i)
E.display()
%3 I2 2 s0 I2->2 I4 4 s2 I4->4 F2 F7 F9 F10 2->F2 2->2 b 3 s1 2->3 a 2->4 a 3->3 a, b 5 s3 4->5 a 6 s4 4->6 b 5->5 a 5->6 b 6->6 a, b 7 s5 7->F7 7->4 a 8 s6 7->8 a 9 s7 7->9 b 8->8 a 10 s8 8->10 b 9->F9 9->9 a, b 10->F10 10->7 a 10->8 b

Accessible

A state is accessible if it may be reached from an initial state.

In [8]:
E.accessible_states()
Out[8]:
[0, 1, 2, 3, 4]

The method accessible returns the restriction of tha tuatomaton to its accessible states (and accessible_here does the same thing in place).

In [9]:
E.accessible().display()
%3 I2 2 s0 I2->2 I4 4 s2 I4->4 F2 2->F2 2->2 b 3 s1 2->3 a 2->4 a 3->3 a, b 5 s3 4->5 a 6 s4 4->6 b 5->5 a 5->6 b 6->6 a, b

Co-accessible

In [10]:
E.display()
%3 I2 2 s0 I2->2 I4 4 s2 I4->4 F2 F7 F9 F10 2->F2 2->2 b 3 s1 2->3 a 2->4 a 3->3 a, b 5 s3 4->5 a 6 s4 4->6 b 5->5 a 5->6 b 6->6 a, b 7 s5 7->F7 7->4 a 8 s6 7->8 a 9 s7 7->9 b 8->8 a 10 s8 8->10 b 9->F9 9->9 a, b 10->F10 10->7 a 10->8 b

A state is co-accessible if there is a path from it to a final state.

In [11]:
E.coaccessible_states()
Out[11]:
[0, 5, 6, 7, 8]

The method coaccessible returns the restriction of tha automaton to its co-accessible states (and coaccessible_here does the same thing in place).

In [12]:
E.coaccessible().display()
%3 I2 2 s0 I2->2 F2 F3 F5 F6 2->F2 2->2 b 3 s1 3->F3 4 s2 3->4 a 5 s3 3->5 b 4->4 a 6 s4 4->6 b 5->F5 5->5 a, b 6->F6 6->3 a 6->4 b

Useful states, trim part

In [13]:
E.display()
%3 I2 2 s0 I2->2 I4 4 s2 I4->4 F2 F7 F9 F10 2->F2 2->2 b 3 s1 2->3 a 2->4 a 3->3 a, b 5 s3 4->5 a 6 s4 4->6 b 5->5 a 5->6 b 6->6 a, b 7 s5 7->F7 7->4 a 8 s6 7->8 a 9 s7 7->9 b 8->8 a 10 s8 8->10 b 9->F9 9->9 a, b 10->F10 10->7 a 10->8 b

A state is useful if there it is both accessible and co-accessible.

In [14]:
E.useful_states()
Out[14]:
[0]

The method trim returns the restriction of tha automaton to its co-accessible states (and trim_here does the same thing in place).

In [15]:
E.trim().display()
%3 I2 2 s0 I2->2 F2 2->F2 2->2 b