automaton.is_synchronized.ipynb

Kernel: Python 3

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:

• automaton.delay_automaton

• automaton.has_bounded_lag

• automaton.synchronize

Examples

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$.

a = ctx.expression(r"a|x+(a|\e)(b|y)").standard()
a

a.is_synchronized()

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.

a = ctx.expression(r"a|x+(b|y)(e|xyz)").standard()
a

a.is_synchronized()

True

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

a = ctx.expression(r"a|x+(b|y)(cde|z)").thompson()
a

a.is_synchronized()

True

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

a.delay_automaton()