automaton.synchronize

Create a new transducer, equivalent to the first one, but where the transitions advance along all the tapes at the same rate, for as long as possible. The transitions before the final states may have the empty word on one of the tapes, to allow for words of different lengths on the input and output.

Preconditions:

  • The input automaton is a transducer.
  • Input.has_bounded_lag

Postconditions:

  • Result.is_synchronized

See also:

Examples

In [1]:
import vcsn
ctx = vcsn.context("lat<law_char, law_char>, b")
ctx
Out[1]:
$\{\ldots\}^* \times \{\ldots\}^*\to\mathbb{B}$

The following automaton is not synchronized (the first transition is already not synchronized):

In [2]:
a = ctx.expression(r"(abc|\e)(d|v)*(\e|wxyz)").standard()
a
Out[2]:
%3 I0 0 0 I0->0 F4 1 1 0->1 abc|ε 3 3 1->3 d|v 4 4 1->4 ε|wxyz 3->3 d|v 3->4 ε|wxyz 4->F4

The lag is bounded, because every cycle (here, the loop) has a lag of 0.

In [3]:
a.has_bounded_lag()
Out[3]:
True

Apart from pure spontaneous transitions, the only transitions with $\varepsilon$ in them are right before the final state.

In [4]:
s = a.synchronize()
s
Out[4]:
%3 I0 0 0:ε|ε I0->0 F4 1 1:abc|ε 0->1 ε|ε 2 3:bcd|ε 1->2 a|v 3 4:ε|z 1->3 abc|wxy 2->3 bcd|wxy 5 3:cdd|ε 2->5 b|v 4 4:ε|ε 3->4 ε|z 4->F4 5->3 cdd|wxy 6 3:ddd|ε 5->6 c|v 6->3 ddd|wxy 6->6 d|v
In [5]:
s.is_synchronized()
Out[5]:
True

This is a (for the most part) letter-to-letter transducer equivalent to the input.

In [6]:
s.proper().letterize().minimize().strip()
Out[6]:
%3 I0 0 0 I0->0 F3 1 1 0->1 a|v 6 6 0->6 a|w 4 4 1->4 b|v 8 8 1->8 b|w 2 2 3 3 2->3 ε|z 3->F3 5 5 4->5 c|v 10 10 4->10 c|w 5->5 d|v 5->10 d|w 7 7 6->7 b|x 7->2 c|y 9 9 8->9 c|x 9->2 d|y 10->9 d|x