expression.zpc(algo="auto")

Generate the ZPC automaton from an expression. Its initial state is final and has the weight of its constant term. It can take an optionnal argument valued with "compact" to enable the compact variant construction.

The algo can be:

  • "auto": same as "regular".
  • "compact": use an alternate implementation for sum and product which requires fewer states.
  • "regular": produce the "pure" version of the ZPC automaton.

Post-condition:

  • Result.is_eps_acyclic()
  • There is no spontaneous path from the initial state to final the state.

Caveats:

  • the context of the result might be different from the original context: spontaneous-transition support is required.

See also:

Examples

The ZPC procedure generates an automaton with spontaneous-transitions, which requires a labelset that feature a "one" label. The nullableset and wordset labelsets (and their compositions) does support a "one" label.

In [1]:
import vcsn
vcsn.B.expression('a[bc]d').zpc()
Out[1]:
%3 I0 0 0 I0->0 F13 1 1 0->1 ε 2 2 1->2 ε 3 3 2->3 a 4 4 3->4 ε 5 5 4->5 ε 7 7 4->7 ε 6 6 5->6 b 9 9 6->9 ε 8 8 7->8 c 8->9 ε 10 10 9->10 ε 11 11 10->11 ε 12 12 11->12 d 13 13 12->13 ε 13->F13

You can also ask for the compact version of the algorithm that way:

In [2]:
vcsn.B.expression('a[bc]d').zpc('compact')
Out[2]:
%3 I0 0 0 I0->0 F7 1 1 0->1 a 2 2 1->2 ε 3 3 2->3 b 4 4 2->4 ε 5 5 3->5 ε 4->5 c 6 6 5->6 ε 7 7 6->7 d 7->F7

You may, however, use a labelset which does not feature a "one", in which case the context of the automaton will be different from the one of the expression.

In [3]:
vcsn.B.expression("a").zpc().context()
Out[3]:
$(\{a, b, c, d, \ldots\})^?\to\mathbb{B}$

Weighted expressions

Weights are supported.

In [4]:
r = vcsn.Q.expression('(<1/3>a*+<1/6>b*)*')
r
Out[4]:
$\left( \left\langle \frac{1}{3} \right\rangle \,{a}^{*} + \left\langle \frac{1}{6} \right\rangle \,{b}^{*}\right)^{*}$
In [5]:
r.zpc()
Out[5]:
%3 I0 0 0 I0->0 F0 F11 0->F0 ⟨2⟩ 1 1 0->1 ⟨2⟩ε 2 2 1->2 ε 6 6 1->6 ε 3 3 2->3 ⟨1/3⟩ε 4 4 3->4 a 4->3 ε 5 5 4->5 ε 10 10 5->10 ε 7 7 6->7 ⟨1/6⟩ε 8 8 7->8 b 8->7 ε 9 9 8->9 ε 9->10 ε 10->1 ⟨2⟩ε 11 11 10->11 ⟨2⟩ε 11->F11

And the compact version:

In [6]:
r.zpc('compact')
Out[6]:
%3 I0 0 0 I0->0 F0 F9 0->F0 ⟨2⟩ 1 1 0->1 ⟨2⟩ε 2 2 1->2 ⟨1/3⟩ε 5 5 1->5 ε 3 3 2->3 a 3->2 ε 4 4 3->4 ε 8 8 4->8 ε 6 6 5->6 ⟨1/6⟩ε 7 7 6->7 b 7->6 ε 7->8 ε 8->1 ⟨2⟩ε 9 9 8->9 ⟨2⟩ε 9->F9