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

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



In [3]:

    
a.context()









    Out[3]:





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



In [4]:

    
p = a.proper(); p









    Out[4]:

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



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



In [9]:

    
a.proper()









    Out[9]:



In [10]:

    
a.proper(prune = False)









    Out[10]:

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 -> $



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>



In [15]:

    
q4.proper()









    Out[15]:

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



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