automaton.is_synchronized

Whether the automaton is synchronized:

  • every transition has the same number of letters on every tape, except for a few leading to final states
  • in each accepting path, disregarding spontaneous transitions, if a $\varepsilon$ is seen on one tape, no more letters will appear on this tape.

Preconditions:

  • automaton is a transducer
  • automaton has bounded lag

Caveat:

  • if the automaton does not have bounded lag, is_synchronized will not terminate.

See also:

Examples

In [1]:
import vcsn
ctx = vcsn.context("lat<law_char, law_char>, b")

The following automaton is not synchronized, because a transition with less letters on the second tape $a| \varepsilon$ is followed by a transition with as many letters on each tape $b|y$.

In [2]:
a = ctx.expression(r"a|x+(a|\e)(b|y)").standard()
a
Out[2]:
%3 I0 0 0 I0->0 F1 F5 1 1 0->1 a|x 3 3 0->3 a|ε 1->F1 5 5 3->5 b|y 5->F5
In [3]:
a.is_synchronized()
Out[3]:
False

This automaton is synchronized, because the transition with less letters on the first tape occurs "at the end" : it is not followed by transitions with more letters on this tape.

In [4]:
a = ctx.expression(r"a|x+(b|y)(e|xyz)").standard()
a
Out[4]:
%3 I0 0 0 I0->0 F1 F5 1 1 0->1 a|x 3 3 0->3 b|y 1->F1 5 5 3->5 e|xyz 5->F5
In [5]:
a.is_synchronized()
Out[5]:
True

Spontaneous transitions are not taken in account when checking for synchronization.

In [6]:
a = ctx.expression(r"a|x+(b|y)(cde|z)").thompson()
a
Out[6]:
%3 I0 0 0 I0->0 F1 2 2 0->2 ε|ε 4 4 0->4 ε|ε 1 1 1->F1 3 3 2->3 a|x 3->1 ε|ε 5 5 4->5 b|y 6 6 5->6 ε|ε 7 7 6->7 cde|z 7->1 ε|ε
In [7]:
a.is_synchronized()
Out[7]:
True

Note that in a synchronized automaton, the corresponding _delay_automaton_ has delays of 0 or strictly increasing (apart from spontaneous transitions).

In [8]:
a.delay_automaton()
Out[8]:
%3 I0 0 0:(0,0) I0->0 F6 F8 1 2:(0,0) 0->1 ε|ε 2 4:(0,0) 0->2 ε|ε 7 3:(0,0) 1->7 a|x 3 5:(0,0) 2->3 b|y 4 6:(0,0) 3->4 ε|ε 5 7:(2,0) 4->5 cde|z 6 1:(2,0) 5->6 ε|ε 6->F6 8 1:(0,0) 7->8 ε|ε 8->F8