# automaton.is_equivalent(aut)¶

Whether this automaton is equivalent to aut, i.e., whether they accept the same words with the same weights.

Preconditions:

• The join of the weightsets is either $\mathbb{B}, \mathbb{Z}$, or a field ($\mathbb{F}_2, \mathbb{Q}, \mathbb{Q}_\text{mp}, \mathbb{R}$).

Algorithm:

• for Boolean automata, check whether is_useless(difference(a1.realtime(), a2.realtime()) and conversely.
• otherwise, check whether is_empty(reduce(union(a1.realtime(), -1 * a2.realtime())).

## Examples¶

In :
import vcsn


Automata with different languages are not equivalent.

In :
Bexp = vcsn.context('lal_char(abc), b').expression
a1 = Bexp('a').standard()
a2 = Bexp('b').standard()
a1.is_equivalent(a2)

Out:
False

Automata that computes different weights are not equivalent.

In :
Zexp = vcsn.context('lal_char, z').expression
a1 = Zexp('<42>a').standard()
a2 = Zexp('<51>a').standard()
a1.is_equivalent(a2)

Out:
False

The types of the automata need not be equal for the automata to be equivalent. In the following example the automaton types are \begin{align} \{a,b,c,x,y\}^* & \rightarrow \mathbb{Q}\\ \{a,b,c,X,Y\} & \rightarrow \mathbb{Z}\\ \end{align}

In :
a = vcsn.context('law_char(abcxy), q').expression('<2>(ab)<3>(c)<5/2>').standard(); a

Out:
In :
b = vcsn.context('lal_char(abcXY), z').expression('<5>ab<3>c').standard(); b

Out:
In :
a.is_equivalent(b)

Out:
True

### Boolean automata¶

Of course the different means to compute automata from rational expressions (thompson, standard, derived_term...) result in different, but equivalent, automata.

In :
r = Bexp('[abc]*')
r

Out:
$\left(a + b + c\right)^{*}$
In :
std = r.standard()
std

Out:
In :
dt = r.derived_term()
dt

Out:
In :
std.is_equivalent(dt)

Out:
True

Labelsets need not to be free. For instance, one can compare the Thompson automaton (which features spontaneous transitions) with the standard automaton:

In :
th = r.thompson()
th

Out:
In :
th.is_equivalent(std)

Out:
True

Of course useless states "do not count" in checking equivalence.

In :
th.proper(prune = False)

Out:
In :
th.proper(prune = False).is_equivalent(std)

Out:
True

### Weighted automata¶

In the case of weighted automata, the algorithms checks whether $(a_1 + -1 \times a_2).\mathtt{reduce}().\mathtt{is\_empty}()$, so the preconditions of automaton.reduce apply.

In :
a = Zexp('<2>ab+<3>ac').automaton()
a

Out:
In :
d = a.determinize()
d

Out:
In :
d.is_equivalent(a)

Out:
True

In particular, beware that for numerical inaccuracy (with $\mathbb{R}$) or overflows (with $\mathbb{Z}$ or $\mathbb{Q}$) may result in incorrect results. Using $\mathbb{Q}_\text{mp}$ is safe.