`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 [1]:

    
import vcsn









    



:0: FutureWarning: IPython widgets are experimental and may change in the future.

Automata with different languages are not equivalent.



In [2]:

    
B = vcsn.context('lal_char(abc), b')
a1 = B.expression('a').standard()
a2 = B.expression('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.expression('<42>a').standard()
a2 = Z.expression('<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]:



In [5]:

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









    Out[5]:



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 = B.expression('[abc]*')
r









    Out[7]:





$\left(a + b + c\right)^{*}$



In [8]:

    
std = r.standard()
std









    Out[8]:



In [9]:

    
dt = r.derived_term()
dt









    Out[9]:



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]:



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]:



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 = Z.expression('<2>ab+<3>ac').automaton()
a









    Out[15]:



In [16]:

    
d = a.determinize()
d









    Out[16]:



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.

automaton.is_equivalent(aut)

Examples

Boolean automata

Weighted automata

`automaton`.`is_equivalent`(`aut`)