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 labelsets of both automata are free
  • The weightset are either $\mathbb{B}, \mathbb{Z}$, or a field ($\mathbb{F}_2, \mathbb{Q}, \mathbb{Q}_\text{mp}, \mathbb{R}$).

See also:

Examples

In [1]: 
import vcsn

Automata with different languages are not equivalent.

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

Automata that computes different weights are not equivalent.

In [3]: 
z = vcsn.context('lal_char, z')
a1 = z.ratexp('<42>a').standard()
a2 = z.ratexp('<51>a').standard()
a1.is_equivalent(a2)
Out[3]:
False

Boolean automata

Of course the different means to compute automata from rational expressions result in different, but equivalent, automata.

In [4]: 
r = b.ratexp('[abc]*')
r
Out[4]:
$\left(a + b + c\right)^{*}$
In [5]: 
std = r.standard()
std
Out[5]:
%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 [6]: 
dt = r.derived_term()
dt
Out[6]:
%3 I0 0 (a+b+c)* I0->0 F0 0->F0 0->0 [a-c]
In [7]: 
std.is_equivalent(dt)
Out[7]:
True

One cannot test the Thompson construction directly, as it results in an automaton whose labelset is not free.

In [8]: 
th = r.ratexp(vcsn.context('lan_char, b')).thompson()
th
Out[8]:
%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 [9]: 
try:
    th.is_equivalent(std)
except Exception as e:
    print("FAIL: " + str(e).splitlines()[0])

FAIL: are_equivalent: no such implementation

It suffices to call proper to address this issue. In addition, we show that that useless states "do not count".

In [10]: 
th.proper(prune = False)
Out[10]:
%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 [11]: 
th.proper(prune = False).is_equivalent(std)
Out[11]:
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 [12]: 
a = z.ratexp('<2>ab+<3>ac').derived_term().strip()
a
Out[12]:
%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 [13]: 
d = a.determinize()
d
Out[13]:
%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 [14]: 
d.is_equivalent(a)
Out[14]:
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.