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

See also:

Examples

In [1]:
import vcsn

Automata with different languages are not equivalent.

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

Automata that computes different weights are not equivalent.

In [3]:
Zexp = vcsn.context('lal_char, z').expression
a1 = Zexp('<42>a').standard()
a2 = Zexp('<51>a').standard()
a1.is_equivalent(a2)
Out[3]:
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 [4]:
a = vcsn.context('law_char(abcxy), q').expression('<2>(ab)<3>(c)<5/2>').standard(); a
Out[4]:
%3 I0 0 0 I0->0 F3 1 1 0->1 ⟨15⟩ab 3 3 1->3 c 3->F3
In [5]:
b = vcsn.context('lal_char(abcXY), z').expression('<5>ab<3>c').standard(); b
Out[5]:
%3 I0 0 0 I0->0 F4 1 1 0->1 ⟨15⟩a 3 3 1->3 b 4 4 3->4 c 4->F4
In [6]:
a.is_equivalent(b)
Out[6]:
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 [7]:
r = Bexp('[abc]*')
r
Out[7]:
$\left(a + b + c\right)^{*}$
In [8]:
std = r.standard()
std
Out[8]:
%3 I0 0 0 I0->0 F0 F1 F3 F4 0->F0 1 1 0->1 a 3 3 0->3 b 4 4 0->4 c 1->F1 1->1 a 1->3 b 1->4 c 3->F3 3->1 a 3->3 b 3->4 c 4->F4 4->1 a 4->3 b 4->4 c
In [9]:
dt = r.derived_term()
dt
Out[9]:
%3 I0 0 (a+b+c)* I0->0 F0 0->F0 0->0 [^]
In [10]:
std.is_equivalent(dt)
Out[10]:
True

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

In [11]:
th = r.thompson()
th
Out[11]:
%3 I8 8 8 I8->8 F9 0 0 2 2 0->2 ε 4 4 0->4 ε 6 6 0->6 ε 1 1 1->0 ε 9 9 1->9 ε 3 3 2->3 a 3->1 ε 5 5 4->5 b 5->1 ε 7 7 6->7 c 7->1 ε 8->0 ε 8->9 ε 9->F9
In [12]:
th.is_equivalent(std)
Out[12]:
True

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

In [13]:
th.proper(prune = False)
Out[13]:
%3 I8 8 8 I8->8 F1 F3 F5 F7 F8 F9 0 0 3 3 0->3 a 5 5 0->5 b 7 7 0->7 c 1 1 1->F1 1->3 a 1->5 b 1->7 c 2 2 2->3 a 3->F3 3->3 a 3->5 b 3->7 c 4 4 4->5 b 5->F5 5->3 a 5->5 b 5->7 c 6 6 6->7 c 7->F7 7->3 a 7->5 b 7->7 c 8->F8 8->3 a 8->5 b 8->7 c 9 9 9->F9
In [14]:
th.proper(prune = False).is_equivalent(std)
Out[14]:
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 [15]:
a = Zexp('<2>ab+<3>ac').automaton()
a
Out[15]:
%3 I0 0 0 I0->0 F3 1 1 0->1 ⟨2⟩a 2 2 0->2 ⟨3⟩a 3 3 1->3 b 2->3 c 3->F3
In [16]:
d = a.determinize()
d
Out[16]:
%3 I0 0 0 I0->0 F2 1 ⟨2⟩1, ⟨3⟩2 0->1 a 2 3 1->2 ⟨2⟩b, ⟨3⟩c 2->F2
In [17]:
d.is_equivalent(a)
Out[17]:
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.