automaton.determinize

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

See also:

Examples

Ladybird

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

In [1]:
import vcsn
lady4 = vcsn.context('lal_char(abc), b').ladybird(3)
lady4

:0: FutureWarning: IPython widgets are experimental and may change in the future.
Out[1]:
%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 a, c 2->2 b, c
In [2]:
lady4d = lady4.determinize()
lady4d
Out[2]:
%3 I0 0 0 I0->0 F0 F3 F5 F6 0->F0 1 1 0->1 a 1->1 b 2 2 1->2 a 3 0, 1 1->3 c 2->0 a 2->2 b 5 0, 2 2->5 c 3->F3 3->1 b 3->3 c 4 1, 2 3->4 a 4->4 b 4->5 a 6 0, 1, 2 4->6 c 5->F5 5->2 b 5->3 a 5->5 c 6->F6 6->4 b 6->6 a, c

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 [3]:
%%automaton a
context = "lal_char(a), b"
0 -> 1 a
%3 0 0 1 1 0->1 a
In [4]:
a.determinize()
Out[4]:
%3

Weighted automata

The algorithm we use requires a division operator. The following example has weights in $\mathbb{Q}$ (and was chosen because the algorithm terminates on it).

In [5]:
%%automaton a
context = "lal_char, q"
$ -> 0 <2>
0 -> 1 <2>a
0 -> 2 <3>a
1 -> 1 <3>b
1 -> 3 <5>c
2 -> 2 <3>b
2 -> 3 <3>d
3 -> $
%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 [6]:
d = a.determinize()
d
Out[6]:
%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 [7]:
a.is_equivalent(d)
Out[7]:
True

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

In [8]:
%%automaton a
context = "lal_char, zmin"
$ -> 0 <0>
0 -> 1 <1>a
0 -> 2 <2>a
1 -> 1 <3>b
1 -> 3 <5>c
2 -> 2 <3>b
2 -> 3 <6>d
3 -> $ <0>
%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 [9]:
d = a.determinize()
d
Out[9]:
%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 automaton.is_equivalent here.

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

Caveats

Some weighted automata cannot be determinized. See automaton.has_twins_property for a possible means to detect whether the procedure will terminate.

The following automaton, for example, admits no equivalent deterministic automaton.

In [12]:
vcsn.context('lal_char, q').expression('a*+(<2>a)*').automaton()
Out[12]:
%3 I0 0 0 I0->0 F0 F1 F2 0->F0 ⟨2⟩ 1 1 0->1 a 2 2 0->2 ⟨2⟩a 1->F1 1->1 a 2->F2 2->2 ⟨2⟩a