automaton.is_deterministic

Whether the automaton is deterministic:

  • at most one initial state
  • each state is deterministic:
    • at most one transition per label

Precondition:

  • labelset is free

See also:

Examples

In [1]:
import vcsn
b = vcsn.context("lal_char(ab), b")

:0: FutureWarning: IPython widgets are experimental and may change in the future.

The empty automaton is deterministic.

In [2]:
a = vcsn.automaton(''' digraph { vcsn_context = "lal_char(ab), b" } ''')
a
Out[2]:
%3
In [3]:
a.is_deterministic()
Out[3]:
True

Having more than one initial state makes the automaton not deterministic.

In [4]:
a = b.expression('a').standard() | b.expression('b').standard()
a
Out[4]:
%3 I0 0 0 I0->0 I2 2 2 I2->2 F1 F3 1 1 0->1 a 1->F1 3 3 2->3 b 3->F3
In [5]:
a.is_deterministic()
Out[5]:
False

Having a state, even unreachable, with two transitions with the same label makes the automaton not deterministic.

In [6]:
a = vcsn.automaton(''' digraph { 
  vcsn_context = "lal_char(ab), b" 
  0 -> 1 [label="a"]
  0 -> 2 [label="a"]
} ''')
a
Out[6]:
%3 0 0 1 1 0->1 a 2 2 0->2 a
In [7]:
a.is_deterministic()
Out[7]:
False