Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 45898
Kernel: Python 3

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 -> $
Image in a Jupyter notebook

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)

abxy\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 -> $
Image in a Jupyter notebook
a.is_functional()
False
a.shortest(10)

abxyabxz\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 -> $
Image in a Jupyter notebook

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
Image in a Jupyter notebook
b.is_ambiguous()
True