Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download
Views: 45856
Kernel: Python 3

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 B\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.

import vcsn lady4 = vcsn.context('lal_char(abc), b').ladybird(3) lady4
Image in a Jupyter notebook
lady4d = lady4.determinize() lady4d
Image in a Jupyter notebook

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

lady4d.strip()
Image in a Jupyter notebook

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).

%%automaton -s a context = "lal_char(a), b" 0 -> 1 a
Image in a Jupyter notebook
a.determinize()
Image in a Jupyter notebook

Weighted automata

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

%%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 -> $
Image in a Jupyter notebook
d = a.determinize() d
Image in a Jupyter notebook

Which is obviously deterministic. Of course they are equivalent:

a.is_equivalent(d)
True

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

%%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>
Image in a Jupyter notebook
d = a.determinize() d
Image in a Jupyter notebook

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

a.shortest(10)

6ac8ad9abc11abd12abbc14abbd15abbbc17abbbd18abbbbc20abbbbd\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}

d.shortest(10)

6ac8ad9abc11abd12abbc14abbd15abbbc17abbbd18abbbbc20abbbbd\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.

a = vcsn.context('lal_char, q').expression('a*+(<2>a)*').automaton() a
Image in a Jupyter notebook

You may however use the lazy determinization in this case.

d = a.determinize(lazy=True) d
Image in a Jupyter notebook
print(d('')); d
2
Image in a Jupyter notebook
print(d('aa')); d
5
Image in a Jupyter notebook
print(d('aaaa')); d
17
Image in a Jupyter notebook

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

d = lady4.determinize(lazy=True) d
Image in a Jupyter notebook
print(d('')); d
1
Image in a Jupyter notebook
d.accessible()
Image in a Jupyter notebook