Awali
Another Weighted Automata library
Data Structures | Functions
Factories & Constructors

Contains all functions that allows to construct automata and expressions. More...

Data Structures

struct  awali::dyn::ratexp_t::with_int_labels
 Helper class that contains convenience factories to build expressions whose labels are integers. More...
 
struct  awali::dyn::ratexp_t::with_tuple_labels
 Helper class that contains convenience factories to build expressions whose labels are tuples. More...
 

Functions

 awali::dyn::automaton_t::automaton_t (context::labelset_description ld, context::weightset_description wd)
 Builds a new empty automaton whose labelset is described by ld and weightset by wd. More...
 
 awali::dyn::ratexp_t::ratexp_t (std::string str, context::labelset_description ld, context::weightset_description wd, bool fixed_alphabet=true)
 Builds the expression represented by str and whose labelset is described by ld and weightset by wd. More...
 
automaton_t awali::dyn::factory::cerny (unsigned n, const std::string &alphabet, const std::string &semiring="B")
 Returns an automaton with n states. More...
 
automaton_t awali::dyn::factory::cerny (unsigned n, int a, int b, const std::string &semiring="B")
 Returns an automaton with n states. More...
 
automaton_t awali::dyn::factory::divkbaseb (unsigned k, unsigned b, const std::string &alphabet="auto", const std::string &semiring="B")
 Returns an automaton which recognizes numbers in base b which are multiple of k. More...
 
automaton_t awali::dyn::factory::double_ring (unsigned n, const std::vector< unsigned > &finals, const std::string &alphabet, const std::string &semiring="B")
 Returns a double ring automaton with n states. More...
 
automaton_t awali::dyn::factory::double_ring (unsigned n, const std::vector< unsigned > &finals, int a, const std::string &semiring="B")
 Returns a double ring automaton with n states. More...
 
static automaton_t awali::dyn::automaton_t::from (std::string alphabet, bool allow_eps_transitions, std::string="B")
 Builds a boolean automaton over given alphabet, that possibly allows eps_transitions. More...
 
static automaton_t awali::dyn::automaton_t::from (std::string alphabet, std::string weightset="B", bool allow_eps_transitions=false)
 Builds an automaton with labels in given alphabet possibly allowing epsilon transitions, and with weights in given weightset. More...
 
static ratexp_t awali::dyn::ratexp_t::with_int_labels::from (std::string str, std::string weightset="B")
 
static ratexp_t awali::dyn::ratexp_t::from (std::string str, std::string weightset="B", std::string alphabet="auto")
 Builds a rational expression from its string representation. More...
 
static ratexp_t awali::dyn::ratexp_t::with_tuple_labels::from (std::string str, std::vector< std::string > alphabets, std::string weightset="B")
 
static ratexp_t awali::dyn::ratexp_t::with_tuple_labels::from (std::string str, unsigned n, std::string weightset="B")
 
static automaton_t awali::dyn::automaton_t::from_context (context_t ctx)
 Builds a new automaton whose labelset and weightset are given by ctx. More...
 
static ratexp_t awali::dyn::ratexp_t::from_context (std::string str, context::labelset_description ld, context::weightset_description wd, bool fixed_alphabet=true)
 
static ratexp_t awali::dyn::ratexp_t::from_context (std::string str, context_t ctx, bool fixed_alphabet=true)
 Builds a rational expression from a string representation and a context. More...
 
static automaton_t awali::dyn::automaton_t::with_int_labels::from_range (int l, int u, bool allow_eps_transitions)
 Builds an automaton with alphabet {l, l+1, ..., u}, possibly allowing epsilon transitions. More...
 
static automaton_t awali::dyn::automaton_t::with_int_labels::from_range (int l, int u, std::string weightset="B", bool allow_eps_transitions=false)
 Builds an automaton with alphabet {l, l+1, ..., u} and weightset weightset More...
 
static ratexp_t awali::dyn::ratexp_t::with_int_labels::from_range (std::string str, int l, int u, std::string weightset="B")
 
static ratexp_t awali::dyn::ratexp_t::with_int_labels::from_size (std::string str, unsigned n, std::string weightset="B")
 
static automaton_t awali::dyn::automaton_t::with_int_labels::from_size (unsigned n, bool allow_eps_transitions)
 Builds a Boolean automaton with alphabet {0, 1, ..., n-1}, possibly allowing epsilon transitions. More...
 
static automaton_t awali::dyn::automaton_t::with_int_labels::from_size (unsigned n, std::string weightset="B", bool allow_eps_transitions=false)
 Builds an automaton with alphabet {0, 1, ..., n-1} and weightset weightset. More...
 
automaton_t awali::dyn::factory::int_divkbaseb (unsigned k, unsigned b, const std::string &semiring="B")
 returns an automaton which recognizes numbers in base b which are multiple of k More...
 
automaton_t awali::dyn::factory::ladybird (unsigned n, const std::string &alphabet, const std::string &semiring="B")
 Returns a "ladybird" automaton with n states. More...
 
automaton_t awali::dyn::factory::ladybird (unsigned n, int a, const std::string &semiring="B")
 Returns an "ladybird" automaton with n states. More...
 
template<typename Context >
mutable_automaton< Context > awali::sttc::n_ultimate (const Context &ctx, typename Context::labelset_t::value_t a, unsigned n)
 Returns an automaton which recognizes words with a specific n-ultimate letter. More...
 
automaton_t awali::dyn::factory::n_ultimate (unsigned n, const std::string &alphabet, const std::string &semiring="B")
 Returns an automaton which recognizes words with a specific n-ultimate letter. More...
 
automaton_t awali::dyn::factory::n_ultimate (unsigned n, int a, int b, const std::string &semiring="B")
 returns an automaton which recognizes words with a specific n-ultimate letter More...
 
automaton_t awali::dyn::factory::randomDFA (unsigned size, std::string alph)
 <> Generates a random deterministic automaton over alphabet alph with size states. More...
 
automaton_t awali::dyn::factory::witness (unsigned n, const std::string &alphabet, const std::string &semiring="B")
 Returns an automaton with n states. More...
 
automaton_t awali::dyn::factory::witness (unsigned n, int a, const std::string &semiring="B")
 Returns an automaton with n states. More...
 

Detailed Description

Contains all functions that allows to construct automata and expressions.

Function Documentation

◆ automaton_t()

awali::dyn::automaton_t::automaton_t ( context::labelset_description  ld,
context::weightset_description  wd 
)

Builds a new empty automaton whose labelset is described by ld and weightset by wd.

Experts only.

This function is the most powerful constructor provided by the dyn layer of Awali. It allows to combine almost arbitrarily all implemented weightset and labelsets.

Example
std::vector<context::labelset_description> v =
{
};
// aut is a transducer with three tapes:
// - first tape holds a letter in {a,b} and no epsilon
// - second tape holds an integer in {12,13,14} or an epsilon
// - third tape holds a word over {b,c,d}
// Each triplet is weighted by a relative integer.
automaton_t()
Buils an automaton_t that is essentially a nullptr; should generally not be used.
labelset_description nullableset(labelset_description ls1)
labelset_description ltupleset(std::vector< labelset_description > lss)
weightset_description weightset(const std::string &k)
labelset_description intletterset(int a, int b)
labelset_description letterset(std::string const &s)
labelset_description wordset(std::string const &s)
Parameters
ldA dynamical description of a labelset
wdA dynamical description of a weightset
Returns
a new empty automaton
Beware
Although this is a constructor for type automaton_t, this might return a transducer depending on ld (as in example above.) If you know that this will produce a transducer, just store it in a variable of type transducer_t:
transducer_t tdc = automaton_t(ld,wd);
See also
Documentation of namespace dyn::context

◆ ratexp_t()

awali::dyn::ratexp_t::ratexp_t ( std::string  str,
context::labelset_description  ld,
context::weightset_description  wd,
bool  fixed_alphabet = true 
)

Builds the expression represented by str and whose labelset is described by ld and weightset by wd.

This function is the most powerful constructor provided by the dyn layer of Awali. It allows to combine almost arbitrarily all implemented weightset and labelsets.

Experts only.

Parameters
strString representation of
ldA description of the labelset
wdA description of the weightset of the ratexp to build
fixed_alphabetIf false, the alphabet of returned ratexp_t will potentially be augmented with letters encountered while parsing str
See also
Documentation of namespace dyn::context

◆ cerny() [1/2]

automaton_t awali::dyn::factory::cerny ( unsigned  n,
const std::string &  alphabet,
const std::string &  semiring = "B" 
)

Returns an automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z.
For every state p,

  • the first letter of the alphabet labels transitions from p to p+1;
  • the other letters label transitions from p to
    • 0 if p =n-1,
    • n -1 otherwise;

State 0 is both initial and final.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

The shortest synchronization word for this automaton has (n -1)^2 letters

Parameters
na positive integer
alphabeta list of letters
semiringthe description of a weightsed
Returns
an automaton with n states
Exceptions
runtime_errorif n is not positive

◆ cerny() [2/2]

automaton_t awali::dyn::factory::cerny ( unsigned  n,
int  a,
int  b,
const std::string &  semiring = "B" 
)

Returns an automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z, over the alphabet [a, b].
For every state p,

  • the first letter of the alphabet labels transitions from p to p+1;
  • the other letters label transitions from p to
    • 0 if p =n-1,
    • n -1 otherwise;

State 0 is both initial and final.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

The shortest synchronization word for this automaton has (n -1)^2 letters

Parameters
na positive integer
aan integer
ban integer larger than a
semiringthe description of a weightsed
Returns
an automaton with n states
Exceptions
runtime_errorif n is not positive

◆ divkbaseb()

automaton_t awali::dyn::factory::divkbaseb ( unsigned  k,
unsigned  b,
const std::string &  alphabet = "auto",
const std::string &  semiring = "B" 
)

Returns an automaton which recognizes numbers in base b which are multiple of k.

The factory builds a deterministic automaton with k states over an alphabet of char. The letters of alphabet are sorted, and the letter with index i represents the digit i. alphabet must contain at least b letters. If the alphabet has more than b letters, the larger letters do not label any transition.
If alphabet is set as "auto", an alphabet of digits is automatically built, capital letters are used for digits larger than 9; the base must be at most 36.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

Parameters
ka positive integer
ba positive integer
alphabetan unordered list of letters
semiringthe description of a weightsed
Returns
an automaton with k states
Exceptions
runtime_errorif k is not positive, or if b is smaller than 2, or if alphabet has less than b letters, or if alphabet is "auto" and b is larger than 36
See also
int_divkbaseb for the factory with int letters.

◆ double_ring() [1/2]

automaton_t awali::dyn::factory::double_ring ( unsigned  n,
const std::vector< unsigned > &  finals,
const std::string &  alphabet,
const std::string &  semiring = "B" 
)

Returns a double ring automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z.
For every state p,

  • the first letter of the alphabet labels transitions from p to p+1;
  • the second one labels transitions from p to p-1;
  • if the alphabet has more than 2 letters, the other letters do not label any transition.

State 0 is initial; finals is the list of the final states.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

Parameters
na positive integer
finalsa vector of states
alphabeta list of letters
semiringthe description of a weightsed
Returns
an automaton with n states
Exceptions
runtime_errorif n is not positive or if alphabet has less than 2 letters

◆ double_ring() [2/2]

automaton_t awali::dyn::factory::double_ring ( unsigned  n,
const std::vector< unsigned > &  finals,
int  a,
const std::string &  semiring = "B" 
)

Returns a double ring automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z, over the alphabet {a,a+1}.
The first letter of the alphabet labels transitions from p to p+1 for every state p, the second one labels transitions from p to p-1. State 0 is initial; finals is the list of the final states.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

Parameters
na positive integer
finalsa vector of states
aan integer
semiringthe description of a weightsed
Returns
an automaton with n states
Exceptions
runtime_errorif n is not positive

◆ from() [1/6]

static automaton_t awali::dyn::automaton_t::from ( std::string  alphabet,
bool  allow_eps_transitions,
std::string  = "B" 
)
static

Builds a boolean automaton over given alphabet, that possibly allows eps_transitions.

Parameters
alphabetString representation of the alphabet of the returned automaton: each char is a letter of the automaton.
allow_eps_transitionsWhether returned automaton should allow epsilon-transitions. Beware of the fact that automata with epsilon-transitions and automata without epsilon-transitions have different static types. Post construction, allowing/disallowing epsilon-transitions always requires a complete copy of the automaton.
Note
This function simply calls:
from(alphabet, "B", allow_eps_transition)
static automaton_t from(std::string alphabet, std::string weightset="B", bool allow_eps_transitions=false)
Builds an automaton with labels in given alphabet possibly allowing epsilon transitions,...
automaton_t allow_eps_transition(automaton_t aut, options_t opts={})
Returns a copy of aut in which epsilon-transitions are allowed.

◆ from() [2/6]

static automaton_t awali::dyn::automaton_t::from ( std::string  alphabet,
std::string  weightset = "B",
bool  allow_eps_transitions = false 
)
static

Builds an automaton with labels in given alphabet possibly allowing epsilon transitions, and with weights in given weightset.

Parameters
alphabetString representation of the alphabet of the returned automaton: each char is a letter of the automaton.
weightsetString representation of the weightset of the built automaton.
allow_eps_transitionsWhether returned automaton should allow epsilon-transitions. Be aware of the fact that automata with epsilon-transitions and automata without epsilon-transitions have different static types. Post construction, allowing/disallowing epsilon-transitions always requires a complete copy of the automaton.
Returns
A new empty automaton.

◆ from() [3/6]

static ratexp_t awali::dyn::ratexp_t::with_int_labels::from ( std::string  str,
std::string  weightset = "B" 
)
static

◆ from() [4/6]

static ratexp_t awali::dyn::ratexp_t::from ( std::string  str,
std::string  weightset = "B",
std::string  alphabet = "auto" 
)
static

Builds a rational expression from its string representation.

Parameters
strString representation of the rational expression to build
weightsetString representation of a weightset.
alphabetIf set to "auto" (default), the alphabet is inferred as part of the construction. Otherwise each caracter is a letter in the alphabet. If you need alphabet {a,u,t,o}, use string "otua".
Returns
a new rational expression.

◆ from() [5/6]

static ratexp_t awali::dyn::ratexp_t::with_tuple_labels::from ( std::string  str,
std::vector< std::string >  alphabets,
std::string  weightset = "B" 
)
static

◆ from() [6/6]

static ratexp_t awali::dyn::ratexp_t::with_tuple_labels::from ( std::string  str,
unsigned  n,
std::string  weightset = "B" 
)
static

◆ from_context() [1/3]

static automaton_t awali::dyn::automaton_t::from_context ( context_t  ctx)
static

Builds a new automaton whose labelset and weightset are given by ctx.

This function is mostly useful for copying context, as in example below.

Example
automaton_t aut = load("a1"); // Here, aut is the automaton that is
// over the context we want to copy
context_t ctx = aut->get_context();
// aut2 is an empty automaton with the same labelset/weightset as aut
static automaton_t from_context(context_t ctx)
Builds a new automaton whose labelset and weightset are given by ctx.
automaton_t load(const std::string &path, options_t opts={})
Loads an automaton from file pointed by path.
Parameters
ctxContext of automaton given
Returns
a new empty automaton
Beware
Although the return type is automaton_t, this might return a transducer depending on ctx. If you know that this will produce a transducer, just store it in a variable of type transducer_t:
transducer_t tdc = automaton_t::from_context(ctx);

◆ from_context() [2/3]

static ratexp_t awali::dyn::ratexp_t::from_context ( std::string  str,
context::labelset_description  ld,
context::weightset_description  wd,
bool  fixed_alphabet = true 
)
static
Deprecated:
Since version 2.1, this function is replaced by the constructor ratexp_t(std::string,context::labelset_description,context::weightset_description,bool).

◆ from_context() [3/3]

static ratexp_t awali::dyn::ratexp_t::from_context ( std::string  str,
context_t  ctx,
bool  fixed_alphabet = true 
)
static

Builds a rational expression from a string representation and a context.

Parameters
strString representation of the rational expresion to build
ctxContext (that is, weightset and labelset) of the rational expression to build
fixed_alphabetIf set to true the function will raise an exception when encountering characters that are not in the labelset; otherwise, it will silently add them to the alphabet.
Returns
a new rational expression

◆ from_range() [1/3]

static automaton_t awali::dyn::automaton_t::with_int_labels::from_range ( int  l,
int  u,
bool  allow_eps_transitions 
)
static

Builds an automaton with alphabet {l, l+1, ..., u}, possibly allowing epsilon transitions.

Parameters
lLower bound of the range
uUpper bound of the range
allow_eps_transitionsIf true, built automaton allows epsilon-transitions.
Returns
A new empty automaton with transitions labelled over integers.

◆ from_range() [2/3]

static automaton_t awali::dyn::automaton_t::with_int_labels::from_range ( int  l,
int  u,
std::string  weightset = "B",
bool  allow_eps_transitions = false 
)
static

Builds an automaton with alphabet {l, l+1, ..., u} and weightset weightset

Parameters
lLower bound of the range.
uUpper bound of the range.
weightset
allow_eps_transitionsIf set to true, built automaton allows epsilon-transitions.
Returns
A new empty automaton.

◆ from_range() [3/3]

static ratexp_t awali::dyn::ratexp_t::with_int_labels::from_range ( std::string  str,
int  l,
int  u,
std::string  weightset = "B" 
)
static

◆ from_size() [1/3]

static ratexp_t awali::dyn::ratexp_t::with_int_labels::from_size ( std::string  str,
unsigned  n,
std::string  weightset = "B" 
)
static

◆ from_size() [2/3]

static automaton_t awali::dyn::automaton_t::with_int_labels::from_size ( unsigned  n,
bool  allow_eps_transitions 
)
static

Builds a Boolean automaton with alphabet {0, 1, ..., n-1}, possibly allowing epsilon transitions.

Parameters
nsize of the alphabet
allow_eps_transitionsIf set to true, built automaton allows epsilon-transitions.
Returns
a new empty automaton.

◆ from_size() [3/3]

static automaton_t awali::dyn::automaton_t::with_int_labels::from_size ( unsigned  n,
std::string  weightset = "B",
bool  allow_eps_transitions = false 
)
static

Builds an automaton with alphabet {0, 1, ..., n-1} and weightset weightset.

Parameters
nsize of the alphabet
weightsetString representation of the weightset of the built automaton
allow_eps_transitionsIf set to true, built automaton allows epsilon-transitions.
Returns
a new empty automaton.

◆ int_divkbaseb()

automaton_t awali::dyn::factory::int_divkbaseb ( unsigned  k,
unsigned  b,
const std::string &  semiring = "B" 
)

returns an automaton which recognizes numbers in base b which are multiple of k

The factory builds a deterministic automaton with k states over the alphabet [0; b]. Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

Parameters
ka positive integer
ba positive integer
semiringthe description of a weightsed
Returns
an automaton with k states
Exceptions
runtime_errorif k is not positive, or if b is smaller than 2

◆ ladybird() [1/2]

automaton_t awali::dyn::factory::ladybird ( unsigned  n,
const std::string &  alphabet,
const std::string &  semiring = "B" 
)

Returns a "ladybird" automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z.
For every state p,

  • the first letter of the alphabet labels transitions from p to p+1;
  • the second letter of the alphabet labels transitions from p to p;
  • the third letter of the alphabet labels transitions from p to p and from p to 0;
    – If the alphabet has more than 3 letters, the other letters do not label any transition. State 0 is both initial and final.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

The minimal automaton of the language accepted by ladybird n has 2^n states.
The name ladybird comes from the shape of the 6-state automaton.

Parameters
na positive integer
alphabetan unordered list of letters
semiringthe description of a weightsed
Returns
an automaton with n states
Exceptions
runtime_errorif n is not positive or if alphabet has less than 3 letters

◆ ladybird() [2/2]

automaton_t awali::dyn::factory::ladybird ( unsigned  n,
int  a,
const std::string &  semiring = "B" 
)

Returns an "ladybird" automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z, over the alphabet {a, a +1, a +2}. For every state p,

  • the first letter of the alphabet labels transitions from p to p+1;
  • the second letter of the alphabet labels transitions from p to p;
  • the third letter of the alphabet labels transitions from p to p and from p to 0;
    State 0 is both initial and final.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

The minimal automaton of the language accepted by ladybird n has 2^n states.
The name ladybird comes from the shape of the 6-state automaton.

Parameters
na positive integer
aan integer
semiringthe description of a weightsed
Returns
an automaton with n states
Exceptions
runtime_errorif n is not positive

◆ n_ultimate() [1/3]

template<typename Context >
mutable_automaton<Context> awali::sttc::n_ultimate ( const Context &  ctx,
typename Context::labelset_t::value_t  a,
unsigned  n 
)

Returns an automaton which recognizes words with a specific n-ultimate letter.

The factory builds an automaton with n +1 states.
The alphabet must contain at least two letters. The automaton accepts every word where the n-ultimate letter is a.

The automaton is co-deterministic hence unambiguous; if weighted, the automaton realizes the characteristic series of the language described above.

Template Parameters
Contextthe type of the context
Parameters
ctxthe context of the automaton
aa label
na positive integer: the position to last of the specified letter
Returns
an automaton with n +1 states
Exceptions
runtime_errorif n is not positive or if the alphabet has less than 2 letters

◆ n_ultimate() [2/3]

automaton_t awali::dyn::factory::n_ultimate ( unsigned  n,
const std::string &  alphabet,
const std::string &  semiring = "B" 
)

Returns an automaton which recognizes words with a specific n-ultimate letter.

The factory builds an automaton with n +1 states that recognizes a language over the alphabet of char.
The alphabet must contain at least two letters. The order of letters in alphabet is significant: the automaton accepts every word where the n-ultimate letter is the first letter of alphabet.

The automaton is co-deterministic hence unambiguous; a semiring for weights can be specified every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

Parameters
na positive integer: the position to last of the specified letter
alphabeta list of letters
semiringthe description of a weightsed
Returns
an automaton with n +1 states
Exceptions
runtime_errorif n is not positive or if alphabet has less than 2 letters

◆ n_ultimate() [3/3]

automaton_t awali::dyn::factory::n_ultimate ( unsigned  n,
int  a,
int  b,
const std::string &  semiring = "B" 
)

returns an automaton which recognizes words with a specific n-ultimate letter

The factory builds an automaton with n +1 states that recognizes a language over the alphabet of integers [a, b].
The alphabet must contain at least two letters. The automaton accepts every word where the n-ultimate letter is a.

The automaton is co-deterministic hence unambiguous; a semiring for weights can be specified every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

Parameters
na positive integer: the position to last of the specified letter
aan integer
ban integer larger than a
semiringthe description of a weightsed
Returns
an automaton with n+1 states
Exceptions
runtime_errorif n is not positive or if b - a is smaller than 1.

◆ randomDFA()

automaton_t awali::dyn::factory::randomDFA ( unsigned  size,
std::string  alph 
)

<> Generates a random deterministic automaton over alphabet alph with size states.

Parameters
sizeThe number of states in the generates
alphAlphabet of the returned automaton
Returns
A new automaton

◆ witness() [1/2]

automaton_t awali::dyn::factory::witness ( unsigned  n,
const std::string &  alphabet,
const std::string &  semiring = "B" 
)

Returns an automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z.
For every state p,

  • the first letter of the alphabet labels transitions from p to p+1;
  • the second letter of the alphabet labels transitions from p to
    • 1 if p=0,
    • 0 if p=1,
    • p otherwise;
  • the third letter of the alphabet labels transitions from p to
    • 0 if p=n -1,
    • p otherwise;
  • the other letters do not label any transition.

State 0 is initial, state n-1 is final.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

This automaton is the "universal witness" described in
Janusz A. Brzozowski and David Liu, Universal Witnesses for State Complexity of Basic Operations Combined with Reversal,
CIAA 2013, Lecture Notes in Computer Science, vol. 7982, pp. 72-83.
doi : 10.1007/978-3-642-39274-0_8

Parameters
nan integer larger than 1
alphabeta list of at least 3 letters
semiringthe description of a weightsed
Returns
an automaton with n states
Exceptions
runtime_errorif n is lesser than 2 or if alphabet has less than 3 letters

◆ witness() [2/2]

automaton_t awali::dyn::factory::witness ( unsigned  n,
int  a,
const std::string &  semiring = "B" 
)

Returns an automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z, over the alphabet {a, a +1, a +2}. For every state p,

  • the first letter of the alphabet labels transitions from p to p+1;
  • the second letter of the alphabet labels transitions from p to
    • 1 if p=0,
    • 0 if p=1,
    • p otherwise;
  • the third letter of the alphabet labels transitions from p to
    • 0 if p=n -1,
    • p otherwise;
  • the other letters do not label any transition.

State 0 is initial, state n-1 is final.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

This automaton is the "universal witness" described in
Janusz A. Brzozowski and David Liu, Universal Witnesses for State Complexity of Basic Operations Combined with Reversal,
CIAA 2013, Lecture Notes in Computer Science, vol. 7982, pp. 72-83.
doi : 10.1007/978-3-642-39274-0_8

Parameters
nan integer larger than 1
aan integer
semiringthe description of a weightsed
Returns
an automaton with n states
Exceptions
runtime_errorif n is lesser than 2