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

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]:
In [3]:
a.context()

Out[3]:
$(\{a, b\})^?\to\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\}\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]:
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

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

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>

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

### 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]:
In [21]:
p = a.proper(lazy=True); p

Out[21]:
In [22]:
p('b'); p

Out[22]:
In [23]:
p('a'); p

Out[23]:
In [24]:
p('abc'); p

Out[24]: