FAdo.rndadfa

Random ADFA generation

ADFA Random generation binding

New in version 1.2.1.

class ADFArnd(n, k=2, s=1)

Sets a random generator for Adfas by sources. By default, s=1 to be initially connected

Variables:

• n (int) – number of states

• k (int) – size of the alphabet

• s (int) – number of sources

Note: For ICDFA s=1

alpha(n, s, k=2)

Number of labeled acyclic initially connected DFA by states and by sources

Parameters:

• k (int) – alphabet size

• n (int) – number of states

• s (int) – number of souces

Return type:

int

Note

uses countAdfabySource

alpha0(n, s, k=2)

Number of labeled acyclic initially connected DFA by states and by sources

Parameters:

• k (int) – alphabet size

• n (int) – number of states

• s (int) – number of souces

Return type:

int

Note

uses gamma instead of beta or rndAdfa

beta(n, s, u, k=2)

Number of valid configurations of transitions

Parameters:

• k (int) – alphabet size

• n (int) – number of states

• s (int) – number of souces

• u (int) – number of souces of n-s

Return type:

int

Note

not used by alpha or rndAdfa

beta0(n, s, u, k=2)

Function beta computed using sets

countAdfaBySources(n, s, k=2)

Number of labelled (initially connected) acyclic automata with n states, alphabet size k, and s sources

Parameters:

• k (int) – alphabet size

• n (int) – number of states

• s (int) – number of souces

Raises:

IndexError – if number of states less than number of sources

gamma(t, u, r)

Parameters:

• t (int) – size of T

• u (int) – size of U

• r (int) – size of r

Return type:

int

rndAdfa(n, s)

Recursively generates a initially connected adfa

Parameters:

• n (int) – number of states

• s (int) – number of sources

See also

Felice & Nicaud, CSR 2013 Lncs 7913, pp 88-99, Random Generation of Deterministic Acyclic Automata Using the Recursive Method, DOI:10.1007/978-3-642-38536-0_8

rndNumberSecondSources(n, s)

Uniformaly random generates the number of secondary sources

Parameters:

• n (int) – number of states

• s (int) – number of sources

Return type:

int

rndTransitionsFromSources(n, s, u)

Generates the transitions from the sources, ensuring that all secondary sources are connected

Parameters:

• n (int) – number of states

• s (int) – number of sources

• u (int) – number of secondary sources

binomial(n, k)

Binomial coeficient

Parameters:

• n – n

• k – k

countadfa(n: int, k: int)

Acyclic (complete) deterministic finite automata structure (unlabeled)

Parameters:

• n ((int)) – number of states

• k ((int)) – alphabetic size

countadfaL(n, k)

Acyclic (complete) deterministic finite automata structure (labeled) initially connected (one dead state)

Parameters:

• n (int) – number of states

• k (int) – alphabetic size

countafa(n, k)

(Quasi) Acyclic deterministic finite automata structure (unlabeled)

countafaL(n, k, r=1)

(Quasi) Acyclic deterministic finite automata structure (labeled)

Parameters:

• n (int) – number of states

• k (int) – alphabetic size

• r (int) – number of dead states

See also

22. 1. Liskovets. Exact enumeration of acyclic deterministic automata. Discrete Applied Mathematics, 154(3):537-551, March 2006.

rndBlockADFA(alpzs: int, nwords: int, blksz: int) → ADFA

Random generation of a block language

Parameters:

• alpzs (int) – alphabet size

• nwords (int) – desired number of words

• blksz (int) – desired size of the block

Returns:

the random block language

Return type:

AFDA

New in version 2.1.3.

surj(n, m)

Counting surgections from [n] to [m]

Parameters:

• n (int) – cardinality of domain

• m (int) – cardinality of image

Note

not used by rndAdfa