automaton.is_isomorphic.ipynb

Kernel: Python 3

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:

• automaton.is_equivalent

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.

import vcsn

def aut(e):
    return vcsn.context('lal_char, b').expression(e, 'binary').standard()
a1 = aut('a*+b*'); a1

a2 = aut('b*+a*'); a2

a1.is_isomorphic(a2), a1 == a2

(True, False)

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

%%automaton -s a1
$ -> 0
0 -> 1 a

%%automaton -s a2
$ -> 0
0 -> 1 b

a1.is_isomorphic(a1), a1.is_isomorphic(a2)

(True, False)

Equivalent automata can be non isomorphic.

a1 = aut('a+a')
a2 = aut('a')
a1.is_isomorphic(a2), a1.is_equivalent(a2)

(False, True)

Weighted Automata

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

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)

True

a1 = aut('<2>a')
a2 = aut('a+a')
a1.is_isomorphic(a2)

False