# 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 :
import vcsn

Out:
In :
lady4d = lady4.determinize()

Out:

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 :
lady4d.strip()

Out:

### 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 :
%%automaton -s a
context = "lal_char(a), b"
0 -> 1 a

In :
a.determinize()

Out:

### 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 :
%%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 :
d = a.determinize()
d

Out:

Which is obviously deterministic. Of course they are equivalent:

In :
a.is_equivalent(d)

Out:
True

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

In :
%%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 :
d = a.determinize()
d

Out:

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

In :
a.shortest(10)

Out:
$\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 :
d.shortest(10)

Out:
$\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 :
a = vcsn.context('lal_char, q').expression('a*+(<2>a)*').automaton()
a

Out:

You may however use the lazy determinization in this case.

In :
d = a.determinize(lazy=True)
d

Out:
In :
print(d('')); d

2

Out:
In :
print(d('aa')); d

5

Out:
In :
print(d('aaaa')); d

17

Out:

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

In :
d = lady4.determinize(lazy=True)
d

Out:
In :
print(d('')); d

1

Out:
In :
d.accessible()

Out: