automaton.delay_automaton

Create a new transducer, equivalent to the first one, with the states labeled with the delay of the state, i.e. the difference of input length on each tape.

Preconditions:

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

Caveat:

  • If the input does not have bounded lag, the construct will not terminate

See also:

Examples

In [1]:
import vcsn
In [2]:
ctx = vcsn.context("lat<law_char, law_char>, b")
ctx
Out[2]:
$\{\ldots\}^* \times \{\ldots\}^*\to\mathbb{B}$
In [3]:
a = ctx.expression(r"'abc, \e''d,v'*'\e,wxyz'").standard()
a
Out[3]:
%3 I0 0 0 I0->0 F4 1 1 0->1 abc|\e 3 3 1->3 d|v 4 4 1->4 \e|wxyz 3->3 d|v 3->4 \e|wxyz 4->F4

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

In [4]:
a.delay_automaton()
Out[4]:
%3 I0 0 0:(0,0) I0->0 F3 1 1:(3,0) 0->1 abc|\e 2 3:(3,0) 1->2 d|v 3 4:(0,1) 1->3 \e|wxyz 2->2 d|v 2->3 \e|wxyz 3->F3

State 1 has a delay of $(3, 0)$ because the first tape is 3 characters longer than the shortest tape (the second one) for all possible inputs leading to this state.

In [5]:
s = ctx.expression(r"(abc|x+ab|y)(d|z)").automaton()
s
Out[5]:
%3 I0 0 0 I0->0 F2 1 1 0->1 ab|y, abc|x 2 2 1->2 d|z 2->F2
In [6]:
s.delay_automaton()
Out[6]:
%3 I0 0 0:(0,0) I0->0 F3 F4 1 1:(1,0) 0->1 ab|y 2 1:(2,0) 0->2 abc|x 4 2:(1,0) 1->4 d|z 3 2:(2,0) 2->3 d|z 3->F3 4->F4

Here, state 1 is split in two, because for one input the delay is $(1, 0)$, and for the other the delay is $(2, 0)$.