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.

Precondition:

automaton is a transducer

Examples



In [1]:

    
import vcsn
ctx = vcsn.context("lat<law_char, law_char>, b")









    



:0: FutureWarning: IPython widgets are experimental and may change in the future.

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]:



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]:



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]:



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]: