automaton.determinize(lazy=False)

Compute the (accessible part of the) determinization of an automaton. When lazy, determinize on-demand (e.g., only states traversed by an evaluation).

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
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 F4 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 4 0, 2 2->4 c 3->F3 3->1 b 3->3 c 5 1, 2 3->5 a 4->F4 4->2 b 4->3 a 4->4 c 5->4 a 5->5 b 6 0, 1, 2 5->6 c 6->F6 6->5 b 6->6 a, c

The resulting automaton has states labeled with subsets of the input automaton set of states. This decoration, like all the others, can be stripped (see automaton.strip):

In [3]:
lady4d.strip()
Out[3]:
%3 I0 0 0 I0->0 F0 F3 F4 F6 0->F0 1 1 0->1 a 1->1 b 2 2 1->2 a 3 3 1->3 c 2->0 a 2->2 b 4 4 2->4 c 3->F3 3->1 b 3->3 c 5 5 3->5 a 4->F4 4->2 b 4->3 a 4->4 c 5->4 a 5->5 b 6 6 5->6 c 6->F6 6->5 b 6->6 a, c

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 -s 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}$ (and was chosen because the algorithm terminates on it).

In [6]:
%%automaton -s 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 [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]:
%%automaton -s 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 [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⟩

They are equivalent, but we cannot use automaton.is_equivalent here.

In [11]:
a.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}$
In [12]:
d.shortest(10)
Out[12]:
$\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 and Lazy Determinization

Some weighted automata cannot be determinized (into a finite automaton). 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 [13]:
a = vcsn.context('lal_char, q').expression('a*+(<2>a)*').automaton()
a
Out[13]:
%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

You may however use the lazy determinization in this case.

In [14]:
d = a.determinize(lazy=True)
d
Out[14]:
%3 I0 0 0 I0->0
In [15]:
print(d('')); d

2
Out[15]:
%3 I0 0 0 I0->0 F0 0->F0 ⟨2⟩ 1 1, ⟨2⟩2 0->1 a
In [16]:
print(d('aa')); d

5
Out[16]:
%3 I0 0 0 I0->0 F0 F1 F2 0->F0 ⟨2⟩ 1 1, ⟨2⟩2 0->1 a 1->F1 ⟨3⟩ 2 1, ⟨4⟩2 1->2 a 2->F2 ⟨5⟩ 3 1, ⟨8⟩2 2->3 a
In [17]:
print(d('aaaa')); d

17
Out[17]:
%3 I0 0 0 I0->0 F0 F1 F2 F3 F4 0->F0 ⟨2⟩ 1 1, ⟨2⟩2 0->1 a 1->F1 ⟨3⟩ 2 1, ⟨4⟩2 1->2 a 2->F2 ⟨5⟩ 3 1, ⟨8⟩2 2->3 a 3->F3 ⟨9⟩ 4 1, ⟨16⟩2 3->4 a 4->F4 ⟨17⟩ 5 1, ⟨32⟩2 4->5 a

To force the full evaluation of a lazy determinization, use automaton.accessible.

In [18]:
d = lady4.determinize(lazy=True)
d
Out[18]:
%3 I0 0 0 I0->0
In [19]:
print(d('')); d

1
Out[19]:
%3 I0 0 0 I0->0 F0 0->F0 1 1 0->1 a
In [20]:
d.accessible()
Out[20]:
%3 I0 0 0 I0->0 F0 F3 F4 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 4 0, 2 2->4 c 3->F3 3->1 b 3->3 c 5 1, 2 3->5 a 4->F4 4->2 b 4->3 a 4->4 c 5->4 a 5->5 b 6 0, 1, 2 5->6 c 6->F6 6->5 b 6->6 a, c