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:

Examples¶

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

In [1]:
import vcsn

Out[1]:
In [2]:
lady4d = lady4.determinize()

Out[2]:

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

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

In [5]:
a.determinize()

Out[5]:

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 ->$

In [7]:
d = a.determinize()
d

Out[7]:

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>

In [10]:
d = a.determinize()
d

Out[10]:

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

You may however use the lazy determinization in this case.

In [14]:
d = a.determinize(lazy=True)
d

Out[14]:
In [15]:
print(d('')); d

2

Out[15]:
In [16]:
print(d('aa')); d

5

Out[16]:
In [17]:
print(d('aaaa')); d

17

Out[17]:

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

In [18]:
d = lady4.determinize(lazy=True)
d

Out[18]:
In [19]:
print(d('')); d

1

Out[19]:
In [20]:
d.accessible()

Out[20]: