automaton.determinize

Computes the (accessible part of the) determinization of an automaton.

Preconditions:

  • its labelset is free
  • its weightset features a division operator (which is the case for $\mathbb{B}$).

Postconditions:

  • the result is deterministic
  • the result is equivalent to the input automaton
  • the result is accessible
  • the result need not be complete

Caveats:

  • might not terminate if the weightset is not $\mathbb{B}$

See also:

Examples

In [1]: 
import vcsn

Ladybird

Ladybird is a well known example that shows the exponential growth on the number of resulting states.

In [2]: 
lady4 = vcsn.context('lal_char(abc), b').ladybird(4)
lady4
Out[2]:
%3 I0 0 0 I0->0 F0 0->F0 1 1 0->1 a 1->0 c 1->1 b, c 2 2 1->2 a 2->0 c 2->2 b, c 3 3 2->3 a 3->0 a, c 3->3 b, c
In [3]: 
lady4d = lady4.determinize()
lady4d
Out[3]:
%3 I0 0 0 I0->0 F0 F3 F6 F8 F9 F10 F12 F13 0->F0 1 1 0->1 a 1->1 b 2 2 1->2 a 3 0, 1 1->3 c 2->2 b 12 0, 2 2->12 c 14 3 2->14 a 3->F3 3->1 b 3->3 c 4 1, 2 3->4 a 4->4 b 5 2, 3 4->5 a 6 0, 1, 2 4->6 c 5->5 b 8 0, 2, 3 5->8 c 13 0, 3 5->13 a 6->F6 6->4 b 6->6 c 7 1, 2, 3 6->7 a 7->7 b 7->8 a 9 0, 1, 2, 3 7->9 c 8->F8 8->5 b 8->8 c 10 0, 1, 3 8->10 a 9->F9 9->7 b 9->9 a, c 10->F10 10->6 a 10->10 c 11 1, 3 10->11 b 11->10 c 11->11 b 11->12 a 12->F12 12->2 b 12->11 a 12->12 c 13->F13 13->3 a 13->13 c 13->14 b 14->0 a 14->13 c 14->14 b

The resulting automaton has states labeled with subsets of the input automaton set of states.

Empty input

If the input automaton has an empty accessible part (i.e., it has no initial state), then the output is empty (which is genuinely displayed as nothing below).

In [4]: 
%%automaton a
context = "lal_char(a), b"
0 -> 1 a
%3 0 0 1 1 0->1 a
In [5]: 
a.determinize()
Out[5]:
%3

Weighted automata

The algorithm we use requires a division operator. The following example has weights in $\mathbb{Q}$.

In [6]: 
a = vcsn.automaton('''digraph
{
  vcsn_context = "lal_char(abcd), q"
  I0 -> 0 [label = "<2>"]
  0 -> 1 [label = "<2>a"]
  0 -> 2 [label = "<3>a"]
  1 -> 1 [label = "<3>b"]
  1 -> 3 [label = "<5>c"]
  2 -> 2 [label = "<3>b"]
  2 -> 3 [label = "<3>d"]
  3 -> F3
}''')
a
Out[6]:
%3 I0 0 0 I0->0 ⟨2⟩ F3 1 1 0->1 ⟨2⟩a 2 2 0->2 ⟨3⟩a 1->1 ⟨3⟩b 3 3 1->3 ⟨5⟩c 2->2 ⟨3⟩b 2->3 ⟨3⟩d 3->F3
In [7]: 
d = a.determinize()
d
Out[7]:
%3 I0 0 0 I0->0 ⟨2⟩ F2 1 1, ⟨3/2⟩2 0->1 ⟨2⟩a 1->1 ⟨3⟩b 2 3 1->2 ⟨5⟩c, ⟨9/2⟩d 2->F2

Which is obviously deterministic. Of course they are equivalent:

In [8]: 
a.is_equivalent(d)
Out[8]:
True

The next example works in $\mathbb{Z}_{\min}$, which features a division: the usual subtraction.

In [9]: 
a = vcsn.automaton('''digraph
{
  vcsn_context = "lal_char(abcd), zmin"
  I0 -> 0
  0 -> 1 [label = "<1>a"]
  0 -> 2 [label = "<2>a"]
  1 -> 1 [label = "<3>b"]
  1 -> 3 [label = "<5>c"]
  2 -> 2 [label = "<3>b"]
  2 -> 3 [label = "<6>d"]
  3 -> F3
}''')
a
Out[9]:
%3 I0 0 0 I0->0 ⟨0⟩ F3 1 1 0->1 ⟨1⟩a 2 2 0->2 ⟨2⟩a 1->1 ⟨3⟩b 3 3 1->3 ⟨5⟩c 2->2 ⟨3⟩b 2->3 ⟨6⟩d 3->F3 ⟨0⟩
In [10]: 
d = a.determinize()
d
Out[10]:
%3 I0 0 ⟨0⟩0 I0->0 ⟨0⟩ F2 1 ⟨0⟩1, ⟨1⟩2 0->1 ⟨1⟩a 1->1 ⟨3⟩b 2 ⟨0⟩3 1->2 ⟨5⟩c, ⟨7⟩d 2->F2 ⟨0⟩

Of course, they are equivalent. However we cannot use is_equivalent here.

In [11]: 
a.shortest(10)
Out[11]:
$\left\langle 6\right\rangle ac \oplus \left\langle 8\right\rangle ad \oplus \left\langle 9\right\rangle abc \oplus \left\langle 11\right\rangle abd \oplus \left\langle 12\right\rangle abbc \oplus \left\langle 14\right\rangle abbd \oplus \left\langle 15\right\rangle abbbc \oplus \left\langle 17\right\rangle abbbd \oplus \left\langle 18\right\rangle abbbbc \oplus \left\langle 20\right\rangle abbbbd$
In [12]: 
d.shortest(10)
Out[12]:
$\left\langle 6\right\rangle ac \oplus \left\langle 8\right\rangle ad \oplus \left\langle 9\right\rangle abc \oplus \left\langle 11\right\rangle abd \oplus \left\langle 12\right\rangle abbc \oplus \left\langle 14\right\rangle abbd \oplus \left\langle 15\right\rangle abbbc \oplus \left\langle 17\right\rangle abbbd \oplus \left\langle 18\right\rangle abbbbc \oplus \left\langle 20\right\rangle abbbbd$