`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

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

In [3]:

q3.is_valid()

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>

In [5]:

q4.proper()

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()

True

In [7]:

t = e.thompson()
t

In [8]:

t.is_valid()

False

automaton.is_valid

Examples

Automaton Q3\mathcal{Q}_3Q3​ (Fig. 2) (in Q\mathbb{Q}Q)

Automaton Q4\mathcal{Q}_4Q4​ (Fig. 3) (in Q\mathbb{Q}Q)

An Invalid Thompson Automaton (Fig. 5)

`automaton.is_valid`

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

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