automaton.is_isomorphic(aut)

Whether this automaton isomorphic to aut, i.e., whether they are "the same graph."

Preconditions:

  • Both automata are accessible

See also:

Examples

Boolean Automata

Automata are isomorphic if there is a bijection between their states.

The following function takes a (Boolean) rational expression, and return its standard automaton.

In [1]:
import vcsn

def aut(e):
    return vcsn.context('lal_char, b').expression(e, 'binary').standard()
a1 = aut('a*+b*'); a1
Out[1]:
%3 I0 0 0 I0->0 F0 F1 F3 0->F0 1 1 0->1 a 3 3 0->3 b 1->F1 1->1 a 3->F3 3->3 b
In [2]:
a2 = aut('b*+a*'); a2
Out[2]:
%3 I0 0 0 I0->0 F0 F1 F3 0->F0 1 1 0->1 b 3 3 0->3 a 1->F1 1->1 b 3->F3 3->3 a
In [3]:
a1.is_isomorphic(a2), a1 == a2
Out[3]:
(True, False)

The automata must be accessible, but coaccessibility is not required.

In [4]:
%%automaton -s a1
$ -> 0
0 -> 1 a
%3 I0 0 0 I0->0 1 1 0->1 a
In [5]:
%%automaton -s a2
$ -> 0
0 -> 1 b
%3 I0 0 0 I0->0 1 1 0->1 b
In [6]:
a1.is_isomorphic(a1), a1.is_isomorphic(a2)
Out[6]:
(True, False)

Equivalent automata can be non isomorphic.

In [7]:
a1 = aut('a+a')
a2 = aut('a')
a1.is_isomorphic(a2), a1.is_equivalent(a2)
Out[7]:
(False, True)

Weighted Automata

We now build automaton weighted in $\mathbb{Q}$.

In [8]:
def aut(e):
    return vcsn.context('lal_char, z').expression(e, 'binary').standard()
a1 = aut('<2>a+<3>b')
a2 = aut('<3>b+<2>a')
a1.is_isomorphic(a2)
Out[8]:
True
In [9]:
a1 = aut('<2>a')
a2 = aut('a+a')
a1.is_isomorphic(a2)
Out[9]:
False