automaton.factor

An automaton that accepts all the factors of the words accepted by an automaton.

Algorithm:

  • Every accessible non-initial state is made initial, with weight one.
  • Every coaccessible non-final state is made final, with weight one.

Preconditions:

  • None

Postconditions:

  • Result == aut.prefix().suffix() == aut.suffix().prefix()

Caveat:

  • While semantically sound for Boolean automata, hardly makes sense on weighted automata.

See also:

Examples

In [1]:
import vcsn
In [2]:
%%automaton -s a
context = "lan_char, q"
$ -> 0 <2>
0 -> 1 <3>a
1 -> 1 <4>b
1 -> 2 <5>\e
2 -> 3 <6>c
3 -> 4 <7>d
3 -> 5 <8>e
4 -> $ <9>
6 -> 0 <10>A
%3 I0 0 0 I0->0 ⟨2⟩ F4 1 1 0->1 ⟨3⟩a 1->1 ⟨4⟩b 2 2 1->2 ⟨5⟩ε 3 3 2->3 ⟨6⟩c 4 4 3->4 ⟨7⟩d 5 5 3->5 ⟨8⟩e 4->F4 ⟨9⟩ 6 6 6->0 ⟨10⟩A
In [3]:
a.factor()
Out[3]:
%3 I0 0 0 I0->0 ⟨2⟩ I1 1 1 I1->1 I2 2 2 I2->2 I3 3 3 I3->3 I4 4 4 I4->4 F0 F1 F2 F3 F4 0->F0 0->1 ⟨3⟩a 1->F1 1->1 ⟨4⟩b 1->2 ⟨5⟩ε 2->F2 2->3 ⟨6⟩c 3->F3 3->4 ⟨7⟩d 5 5 3->5 ⟨8⟩e 4->F4 ⟨9⟩ 6 6 6->0 ⟨10⟩A