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

import vcsn

Simple Cases

%%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 -> $

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

a.is_functional()

True

a.shortest(10)

$\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.

%%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 -> $

a.is_functional()

False

a.shortest(10)

$\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.

%%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 -> $

This transducer is functional:

a.is_functional()

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.

b = a.focus(0)
b

b.is_ambiguous()

True