automaton.proper(prune=True, backward=False)

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

Arguments:

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

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 vcsn

:0: FutureWarning: IPython widgets are experimental and may change in the future.

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\})^?\rightarrow\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\}\rightarrow\mathbb{B}$

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

In [6]:
a.proper(backward = False)
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(backward = False))
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 3 1->3 ε 2 2 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 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(e)

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