automaton.shortest.ipynb

Kernel: Python 3

automaton.shortest(num = None, len = None)

Return a (finite) approximation of the behavior of the automaton controled by the length of the words. In other words, compute the polynomial of the first accepted words (according to the shortlex order), and their associated weight.

Arguments:

• num the number of words to find (there might be fewer). None stands for $\infty$ if len is specified, 1 otherwise.

• len the maximum length of the words to find. None stands for $\infty$.

Default values are handled as follows:

	len = None	len = $\ell$
num = None	$1, \infty$	$\infty, \ell$
num = $n$	$n, \infty$	$n, \ell$

Preconditions:

• the automaton must not have spontaneous cycles

See also:

• automaton.evaluate

• automaton.lightest

• expression.shortest

Examples

import vcsn

Boolean Automata

a = vcsn.context('lal_char(ab), b').de_bruijn(1)
a

Calling a.shortest() is equivalent to a.shortest(1) which is equivalent to a.shortest(1, 0): find the shortest word, whatever its length:

a.shortest()

$\mathit{aa}$

To get the first four words, use a.shortest(4) (or a.shortest(len = 4)):

a.shortest(4)

$\mathit{aa} \oplus \mathit{ab} \oplus \mathit{aaa} \oplus \mathit{aab}$

The words with at most four letters:

a.shortest(len=4)

$\mathit{aa} \oplus \mathit{ab} \oplus \mathit{aaa} \oplus \mathit{aab} \oplus \mathit{baa} \oplus \mathit{bab} \oplus \mathit{aaaa} \oplus \mathit{aaab} \oplus \mathit{abaa} \oplus \mathit{abab} \oplus \mathit{baaa} \oplus \mathit{baab} \oplus \mathit{bbaa} \oplus \mathit{bbab}$

At most 10 words of at most 4 letters:

a.shortest(num=10, len=4)

$\mathit{aa} \oplus \mathit{ab} \oplus \mathit{aaa} \oplus \mathit{aab} \oplus \mathit{baa} \oplus \mathit{bab} \oplus \mathit{aaaa} \oplus \mathit{aaab} \oplus \mathit{abaa} \oplus \mathit{abab}$

At most 10 words of at most 3 letters:

a.shortest(num=10, len=3)

$\mathit{aa} \oplus \mathit{ab} \oplus \mathit{aaa} \oplus \mathit{aab} \oplus \mathit{baa} \oplus \mathit{bab}$

Weighted Automata

The following automaton decodes binary numbers.

%%automaton -s bin
context = "lal_char(01), z"
$ -> 0
0 -> 0 0, 1
0 -> 1 1
1 -> $
1 -> 1 <2>0, <2>1

bin.shortest(len=3)

$\mathit{1} \oplus \mathit{01} \oplus \left\langle 2\right\rangle \mathit{10} \oplus \left\langle 3\right\rangle \mathit{11} \oplus \mathit{001} \oplus \left\langle 2\right\rangle \mathit{010} \oplus \left\langle 3\right\rangle \mathit{011} \oplus \left\langle 4\right\rangle \mathit{100} \oplus \left\langle 5\right\rangle \mathit{101} \oplus \left\langle 6\right\rangle \mathit{110} \oplus \left\langle 7\right\rangle \mathit{111}$

bin.shortest(num=10)

$\mathit{1} \oplus \mathit{01} \oplus \left\langle 2\right\rangle \mathit{10} \oplus \left\langle 3\right\rangle \mathit{11} \oplus \mathit{001} \oplus \left\langle 2\right\rangle \mathit{010} \oplus \left\langle 3\right\rangle \mathit{011} \oplus \left\langle 4\right\rangle \mathit{100} \oplus \left\langle 5\right\rangle \mathit{101} \oplus \left\langle 6\right\rangle \mathit{110}$

Transducers

The following automaton maps words to words. The length of a multitape words is the largest length of its components: $\mathsf{len}(abc|x) = 3$.

%%automaton -s t
context = "lat<law<char>, law<char>>, q"
$ -> 0
0 -> 1 <1>one|un
0 -> 2 <2>two|deux
0 -> 3 <3>three|trois
1 -> 0 \e|\e
2 -> 0 \e|\e
3 -> 0 \e|\e
1 -> $
2 -> $
3 -> $

t.shortest(num=10, len=9)

$\mathit{one}|\mathit{un} \oplus \left\langle 2\right\rangle \mathit{two}|\mathit{deux} \oplus \left\langle 3\right\rangle \mathit{three}|\mathit{trois} \oplus \mathit{oneone}|\mathit{unun} \oplus \left\langle 2\right\rangle \mathit{onetwo}|\mathit{undeux} \oplus \left\langle 2\right\rangle \mathit{twoone}|\mathit{deuxun} \oplus \left\langle 4\right\rangle \mathit{twotwo}|\mathit{deuxdeux} \oplus \left\langle 3\right\rangle \mathit{onethree}|\mathit{untrois} \oplus \left\langle 3\right\rangle \mathit{threeone}|\mathit{troisun} \oplus \left\langle 6\right\rangle \mathit{threetwo}|\mathit{troisdeux}$