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:

References:

Examples

In [1]:
import sys, vcsn

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

In [2]:
a = vcsn.context('lal_char(ab), b').expression('(ab)*').thompson(); a
Out[2]:
%3 I4 4 4 I4->4 F5 0 0 1 1 0->1 a 2 2 1->2 ε 3 3 2->3 b 3->0 ε 5 5 3->5 ε 4->0 ε 4->5 ε 5->F5
In [3]:
a.context()
Out[3]:
$(\{a, b\})^?\to\mathbb{B}$
In [4]:
p = a.proper(); p
Out[4]:
%3 I2 2 2 I2->2 F1 F2 0 0 1 1 0->1 b 1->F1 1->0 a 2->F2 2->0 a

Note that the resulting context is no longer nullable.

In [5]:
p.context()
Out[5]:
$\{a, b\}\to\mathbb{B}$

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

In [6]:
a.proper(direction="forward")
Out[6]:
%3 I0 0 0 I0->0 I2 2 2 I2->2 F2 1 1 0->1 a 1->0 b 1->2 b 2->F2
In [7]:
a.proper().is_equivalent(a.proper(direction="backward"))
Out[7]:
True

Pruning

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

In [8]:
%%automaton a
vcsn_context = "lan_char(abc), b"
I -> 0
0 -> 1 a
1 -> F
i -> 0 a
1 -> f \e
%3 I0 0 0 I0->0 F1 1 1 0->1 a 1->F1 3 f 1->3 ε 2 i 2->0 a
In [9]:
a.proper()
Out[9]:
%3 I0 0 0 I0->0 F1 1 1 0->1 a 1->F1 2 2 2->0 a
In [10]:
a.proper(prune=False)
Out[10]:
%3 I0 0 0 I0->0 F1 1 1 0->1 a 1->F1 2 2 2->0 a 3 3

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.

In [11]:
%%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 -> $
%3 I0 0 0 I0->0 F0 0->F0 0->0 ⟨-1/2⟩ε 1 1 0->1 ⟨1/2⟩ε 1->0 ⟨1/2⟩ε 1->1 ⟨-1/2⟩ε
In [12]:
try:
  q3.proper()
except Exception as e:
  print("error:", e, file=sys.stderr)

error: proper: invalid automaton
In [13]:
q3.is_valid()
Out[13]:
False

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

In [14]:
%%automaton q4
context = "lan_char, q"
$ -> 0
0 -> 1 <1/2>\e, a
1 -> 0 <-1>\e, b
1 -> $ <2>
%3 I0 0 0 I0->0 F1 1 1 0->1 ⟨1/2⟩ε, a 1->F1 ⟨2⟩ 1->0 ⟨-1⟩ε, b
In [15]:
q4.proper()
Out[15]:
%3 I0 0 0 I0->0 F0 F1 0->F0 ⟨2/3⟩ 0->0 ⟨1/3⟩b 1 1 0->1 ⟨2/3⟩a 1->F1 ⟨4/3⟩ 1->0 ⟨2/3⟩b 1->1 ⟨-2/3⟩a

A Thompson Automaton (Fig. 5)

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

In [16]:
e = vcsn.context('lal_char, q').expression('(a*+<-1>b*)*')
t = e.thompson()
t
Out[16]:
%3 I10 10 10 I10->10 F11 0 0 4 4 0->4 ε 8 8 0->8 ε 1 1 1->0 ε 11 11 1->11 ε 2 2 3 3 2->3 a 3->2 ε 5 5 3->5 ε 4->2 ε 4->5 ε 5->1 ε 6 6 7 7 6->7 b 7->6 ε 9 9 7->9 ε 8->6 ⟨-1⟩ε 8->9 ⟨-1⟩ε 9->1 ε 10->0 ε 10->11 ε 11->F11
In [17]:
t.is_valid()
Out[17]:
False
In [18]:
e.is_valid()
Out[18]:
True

Other constructs, such as standard, work properly.

In [19]:
e.standard()
Out[19]:
%3 I0 0 0 I0->0 F0 F1 F3 0->F0 1 1 0->1 a 3 3 0->3 ⟨-1⟩b 1->F1 1->1 ⟨2⟩a 1->3 ⟨-1⟩b 3->F3 3->1 a

Lazy Proper

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

In [20]:
a = vcsn.context('lal_char, b').expression('(ab)*c').thompson(); a
Out[20]:
%3 I4 4 4 I4->4 F7 0 0 1 1 0->1 a 2 2 1->2 ε 3 3 2->3 b 3->0 ε 5 5 3->5 ε 4->0 ε 4->5 ε 6 6 5->6 ε 7 7 6->7 c 7->F7
In [21]:
p = a.proper(lazy=True); p
Out[21]:
%3 I0 0 0 I0->0 I6 6 6 I6->6 F7
In [22]:
p('b'); p
Out[22]:
%3 I0 0 0 I0->0 I6 6 6 I6->6 F7 2 2 0->2 a 7 7 6->7 c
In [23]:
p('a'); p
Out[23]:
%3 I0 0 0 I0->0 I6 6 6 I6->6 F7 2 2 0->2 a 2->0 b 2->6 b 7 7 6->7 c
In [24]:
p('abc'); p
Out[24]:
%3 I0 0 0 I0->0 I6 6 6 I6->6 F7 2 2 0->2 a 2->0 b 2->6 b 7 7 6->7 c 7->F7