Classical transformations

Graphs

# We disable autosave for technical reasons.
# Replace 0 by 120 in next line to restore default.
%autosave 0

Autosave disabled

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 make_random_DFA produces a strongly connected automaton, hence the sligthly convoluted code below. )

A = awalipy.make_random_DFA(2,"ab")
B = awalipy.make_random_DFA(3,"ab")
C = awalipy.make_random_DFA(4,"ab")
D = A.sum(B).sum(C)
s = D.states()
D.set_final(s[1])
D.set_final(s[4])
D.set_transition(s[0],s[2],"a")
D.set_transition(s[5],s[2],"a")
D.display()

---

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

D.sccs()

[[4, 3, 2], [1], [0], [8, 7, 6, 5]]

---

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

D.scc_of(4)

[2, 3, 4]

---

The method condensation() gives (as an Automaton), the Directed Acyclic graph of the sccs of the considered automaton.

D.condensation().display(history=True)

Accessible, co-accessible, trim

E = D.copy()
E.display()

s = E.states()
for i in [5,6,7,8] :
    E.unset_initial(s[i])
for i in [2,3,4] :
    E.unset_final(s[i])
E.display()

Accessible

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

E.accessible_states()

[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).

E.accessible().display()

Co-accessible

E.display()

---

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

E.coaccessible_states()

[0, 1, 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).

E.coaccessible().display()

Useful states, trim part

E.display()

---

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

E.useful_states()

[0, 1]

---

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

E.trim().display()