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

Simple Cases

In [2]:
%%automaton -s a
context = "lat<lal_char, lal_char>, b"
$ -> 0
0 -> 1 a|x
0 -> 2 a|x
1 -> 3 b|y
2 -> 3 b|y
3 -> $
%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]:
$\mathit{ab}|\mathit{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 -s a
context = "lat<lal_char, lal_char>, b"
$ -> 0
0 -> 1 a|x
0 -> 2 a|x
1 -> 3 b|y
2 -> 3 b|z
3 -> $
%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]:
$\mathit{ab}|\mathit{xy} \oplus \mathit{ab}|\mathit{xz}$

A More Complex Example

The following example (Figure 3 from beal.2003.tcs) shows a transducer whose input automaton is ambiguous, yet the transduder is functional.

In [8]:
%%automaton -s a
context = "lat<lal_char, law_char>, b"
$ -> 0
0 -> $
0 -> 1 a|x
0 -> 2 a|xxx
1 -> 2 a|xxxx
1 -> 3 a|xxx
2 -> 3 a|x
3 -> 0 a|xx
$ -> 3
3 -> $
%3 I0 0 0 I0->0 I3 3 3 I3->3 F0 F3 0->F0 1 1 0->1 a|x 2 2 0->2 a|xxx 1->2 a|xxxx 1->3 a|xxx 2->3 a|x 3->F3 3->0 a|xx

This transducer is functional:

In [9]:
a.is_functional()
Out[9]:
True

If we focus on the "input automaton", in other words, on the tape 0 of this transducer, we can see that it is ambigous.

In [10]:
b = a.focus(0)
b
Out[10]:
%3 I0 0 0 I0->0 I3 3 3 I3->3 F0 F3 0->F0 1 1 0->1 a 2 2 0->2 a 1->2 a 1->3 a 2->3 a 3->F3 3->0 a
In [11]:
b.is_ambiguous()
Out[11]:
True