# automaton module¶

This module contains the Automaton class

class automaton.Automaton(nbL=0, nbS=0, initial=[], final=[], transitions=[])[source]

Bases: object

Define an automaton with parameters

• Input:
Parameters: nbL (int) – the number of letters nbS (int) – the number of states initial (list) – the initial vector final (list) – the final vector transition (list) – the transitions tables
BuildHankels(lrows=[], lcolumns=[])[source]

Return all Hankel (denses) matrices built on lrows and lcolumns

• Input:
Parameters: lrows (list) – lcolumns (list) –
• Output:
Returns: list of all Hankel matrices built on lrows and lcolumns list
HouseholderReductionFw(tau)[source]

algorithm (Fig. 3) from the paper Stability and complexity of Minimising Probabilistic Automata by Kiefer and Wachter

• Input:
Parameters: self (Automaton) – an object of the automaton class tau (float) – error tolerance parameter >=0
• Output:
Returns: The canonical forward reduction computed to the tolerance tau Automaton
static HouseholderReflector(x)[source]

the vector which defines the Householder for x

• Input:
Parameters: x (vector) – a vector in R^k different from 0
• Output:
Returns: v = u/||u|| where u_1 = x_1 + sign(x_1)||x|| and u_i = x_i for i \geq 2 vector
static SimpleExample()[source]

A Probabilistic Automaton with two states and two letters.

• Output:
Returns: An automaton instance example with simple values Automaton
calc_prefix_completion_weights(prefix)[source]

a sufficient condition to be absolutely convergent

• Input:
Parameters: self (Automaton) – Be careful that A should be a prefix transformation of an Automata. (see transformation()) prefix (List) – list of integers representing a prefix
• Output:
Returns: a dictionary with all alphabet letters as keys. The associated values are the weights of being the next letter. dict
final

The vector containing the final weight of each state

initial

The vector containing the initial weight of each state

isAbsConv

Does the automaton meet the sufficient condition to be absolutely convergent

static load_Spice_Automaton(adr)[source]

Load an automaton from a SPiCe file and returns an object of the class Automaton; works for PFA and PDFA - not for HMM.

minimisation(tau)[source]

compute an equivalent minimal automaton, to the precision tau

• Input:
Parameters: self (Automaton) –
• Output:
Returns: B, equivalent to A with a minimal number of states Automaton
mirror()[source]

Compute the mirror automaton

• Input:
Parameters: self (Automaton) – Automaton(nbL, nbS, initial, final, transitions)
• Output:
Returns: mA = Automaton(nbL, nbS, final, initial, Newtransitions) where Newtransitions[x] = transpose(transitions[x]) Automaton
static mulHouseholderReflector(u, v)[source]

the product of u by the HouseholderReflector nxn matrix based on v

• Input:
Parameters: u (vector) – row vector of R^n v (vector) – vector of R^k (k<=n)
• Output:
Returns: w, row vector of R^n, w = uP(v) where P(v)=[I_{n-k} 0; 0 R]\in R^{n \times n} and R=I_k-2v^T.v vector
nbL

The number of letters

nbS

The number of states

sum()[source]

the sum of a rational series

transformation(source='classic', target='prefix')[source]

Takes an automaton as input and transforms it.

• Input:
Parameters: source (str) – “prefix”, “factor” or “classic” (default) target (str) – “prefix” (default), “factor” or “classic”
• Output:
Returns: The result automaton instance AutomatonThe transformation is done according to the source and target parameters. .. warning:: it does not check the convergence
transitions

The list of arrays defining the transitions

val(word)[source]

Compute the value computed by the automaton on word

• Input:
Parameters: self (Automaton) – weighted automaton word (str) – a string
• Output:
Returns: probability r_A(w) float