automaton
.proper(prune=True
, backward=True
, algo="auto"
, lazy=False)
¶Create an equivalent automaton without 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:
is_valid
.Postconditions:
See also:
References:
import 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()
p = a.proper(); p
Note that the resulting context is no longer nullable.
p.context()
The closure can be run "forwardly" instead of "backwardly", which the default (sort of a "coproper"):
a.proper(backward = False)
a.proper().is_equivalent(a.proper(backward = False))
States that become inaccessible are removed. To remove this pruning, pass prune=False
to proper
:
%%automaton a
vcsn_context = "lan_char(abc), b"
I -> 0
0 -> 1 a
1 -> F
i -> 0 a
1 -> f \e
a.proper()
a.proper(prune=False)
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.
The following automaton might seem well-defined. Actually, it is not, as properly diagnosed.
%%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 -> $
try:
q3.proper()
except Exception as e:
print(e)
q3.is_valid()
%%automaton q4
context = "lan_char, q"
$ -> 0
0 -> 1 <1/2>\e, a
1 -> 0 <-1>\e, b
1 -> $ <2>
q4.proper()
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()
e.is_valid()
Other constructs, such as standard
, work properly.
e.standard()
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