automaton.is_valid

A careful analysis of automata with spontaneous transitions shows that in some case, spontaneous-cycles may result in automata with an undefined behavior. They are called invalid.

Preconditions:

  • None

See also:

References:

Examples

In [1]:
import vcsn

The following examples are taken from lombardy.2013.ijac.

Automaton $\mathcal{Q}_3$ (Fig. 2) (in $\mathbb{Q}$)

The following automaton is invalid.

In [2]:
%%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 [3]:
q3.is_valid()
Out[3]:
False

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

The following one, however, is valid. Spontaneous transitions can be eliminated.

In [4]:
%%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 [5]:
q4.proper()
Out[5]:
%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

An Invalid Thompson Automaton (Fig. 5)

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

In [6]:
e = vcsn.context('lal_char, q').expression('(a*+<-1>b*)*')
e.is_valid()
Out[6]:
True
In [7]:
t = e.thompson()
t
Out[7]:
%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 [8]:
t.is_valid()
Out[8]:
False