automaton.is_functional

Whether the automaton is functional, i.e. each input (string) is transduced to a unique output (string). There may be multiple paths, however, that contain this input and output string pair.

Precondition:

  • The automaton is transducer

Examples

In [1]: 
import vcsn
In [2]: 
%%automaton a dot
digraph {                                                                                                                                              
  vcsn_context = "lat<lal_char(abc),lal_char(xyz)>, b"                                                                                                                         
  I0 -> 0                                                                                                                                                                     
  0 -> 1 [label = "(a, x)"]                                                                                                                                                   
  0 -> 2 [label = "(a, x)"]                                                                                                                                                   
  1 -> 3 [label = "(b, y)"]                                                                                                                                                   
  2 -> 3 [label = "(b, y)"]                                                                                                                                                   
  3 -> F3                                                                                                                                                                     
}
%3 I0 0 0 I0->0 F3 1 1 0->1 (a,x) 2 2 0->2 (a,x) 3 3 1->3 (b,y) 2->3 (b,y) 3->F3

This transducer is functional, as can also be seen from its series (computed thanks to automaton.shortest): it uniquely maps ab to xy.

In [3]: 
a.is_functional()
Out[3]:
True
In [4]: 
a.shortest(10)
Out[4]:
$(ab,xy)$

However, the following transducer is not functional, as it maps ab to both xy and xz, again, as demonstrated by shortest.

In [5]: 
%%automaton a dot
digraph {                                                                                                                                               
  vcsn_context = "lat<lal_char(abc),lal_char(xyz)>, b"                                                                                                                         
  I0 -> 0                                                                                                                                                                     
  0 -> 1 [label = "(a, x)"]                                                                                                                                                   
  0 -> 2 [label = "(a, x)"]                                                                                                                                                   
  1 -> 3 [label = "(b, y)"]                                                                                                                                                   
  2 -> 3 [label = "(b, z)"]                                                                                                                                                   
  3 -> F3                                                                                                                                                                     
}
%3 I0 0 0 I0->0 F3 1 1 0->1 (a,x) 2 2 0->2 (a,x) 3 3 1->3 (b,y) 2->3 (b,z) 3->F3
In [6]: 
a.is_functional()
Out[6]:
False
In [7]: 
a.shortest(10)
Out[7]:
$(ab,xy) \oplus (ab,xz)$