automaton.proper.ipynb

Kernel: Python 3

automaton.proper(direction="backward", prune=True, algo="auto", lazy=False)

Create an equivalent automaton without spontaneous transitions (i.e., transitions labeled by \e).

Arguments:

• direction whether to perform "backward" closure, or "forward" closure.

• prune whether to remove the states that become inaccessible (or non coaccsessible in the case of forward closure).

• algo the algorithm to compute the proper automaton.

• lazy whether performing the computation lazily, on the fly.

Preconditions:

• The automaton is_valid.

Postconditions:

• Result is proper.

• If possible, the context of Result is no longer nullable.

See also:

• Contexts

• automaton.is_proper

• automaton.is_valid

References:

• lombardy.2013.ijac

Examples

import sys, vcsn

The typical use of proper is to remove spontaneous transitions from a Thompson automaton.

a = vcsn.context('lal_char(ab), b').expression('(ab)*').thompson(); a

a.context()

$(\{a, b\})^?\to\mathbb{B}$

p = a.proper(); p

Note that the resulting context is no longer nullable.

p.context()

$\{a, b\}\to\mathbb{B}$

The closure can be run "forwardly" instead of "backwardly", which the default (sort of a "coproper"):

a.proper(direction="forward")

a.proper().is_equivalent(a.proper(direction="backward"))

True

Pruning

States that become inaccessible are removed. To remove this pruning, pass prune=False to proper:

%%automaton a
vcsn_context = "lan_char(abc), b"
$ -> 0
0 -> 1 a
1 -> $
i -> 0 a
1 -> f \e

a.proper()

a.proper(prune=False)

Weighted Automata

The implementation of proper in Vcsn is careful about the validity of the automata. In particular, the handling on spontaneous-cycles depends on the nature of the weightset. Some corner cases from lombardy.2013.ijac include the following ones.

Automaton $\mathcal{Q}_3$ (Fig. 2) (in $\mathbb{Q}$)

The following automaton might seem well-defined. Actually, it is not, as properly diagnosed.

%%automaton -s q3
context = "lan_char, q"
$ -> 0
0 -> 0 <-1/2>\e
0 -> 1  <1/2>\e
1 -> 1 <-1/2>\e
1 -> 0  <1/2>\e
0 -> $

try:
  q3.proper()
except Exception as e:
  print("error:", e, file=sys.stderr)

error: proper: invalid automaton

q3.is_valid()

False

Automaton $\mathcal{Q}_4$ (Fig. 3) (in $\mathbb{Q}$)

%%automaton q4
context = "lan_char, q"
$ -> 0
0 -> 1 <1/2>\e, a
1 -> 0 <-1>\e, b
1 -> $ <2>

q4.proper()

A Thompson Automaton (Fig. 5)

Sadly enough, the (weighted) Thompson construction may build invalid automata from valid expressions.

e = vcsn.context('lal_char, q').expression('(a*+<-1>b*)*')
t = e.thompson()
t

t.is_valid()

False

e.is_valid()

True

Other constructs, such as standard, work properly.

e.standard()

Lazy Proper

Instead of completely eliminating the spontaneous transitions from the automaton, it is possible to delay the elimination until needed.

a = vcsn.context('lal_char, b').expression('(ab)*c').thompson(); a

p = a.proper(lazy=True); p

p('b'); p

p('a'); p

p('abc'); p