FAdo.fl

Finite languages and related automata manipulation

Finite languages manipulation

class ADFA

Acyclic Deterministic Finite Automata class

Changed in version 1.3.3.

addSuffix(st, w)

Adds a suffix starting in st

Parameters:

• st (int) – state

• w (Word) – suffix

New in version 1.3.3.

Attention

in place transformation

complete(dead=None)

Make the ADFA complete

Parameters:

dead (int, optional) – a state to be identified as dead state if one was not identified yet

Attention

The object is modified in place

Changed in version 1.3.3.

diss()

Evaluates the dissimilarity language

Return type:

FL

New in version 1.2.1.

dissMin(witnesses=None)

Evaluates the minimal dissimilarity language

Parameters:

witnesses (dict) – optional witness dictionay

Return type:

FL

New in version 1.2.1.

dup()

Duplicate the basic structure into a new ADFA. Basically a copy.deep.

Return type:

ADFA

forceToDFA()

Conversion to DFA

Return type:

DFA

forceToDFCA()

Conversion to DFCA

Return type:

DFA

level()

Computes the level for each state

Returns:

levels of states

Return type:

dict

New in version 0.9.8.

minDFCA()

Generates a minimal deterministic cover automata from a DFA

Return type:

DCFA

New in version 0.9.8.

See also

Cezar Campeanu, Andrei Päun, and Sheng Yu, An efficient algorithm for constructing minimal cover automata for finite languages, IJFCS

minReversible()

Returns the minimal reversible equivalent automaton

Return type:

ADFA

minimal()

Finds the minimal equivalent ADFA

Returns:

the minimal equivalent ADFA

Return type:

DFA

See also

[TCS 92 pp 181-189] Minimisation of acyclic deterministic automata in linear time, Dominique Revuz

Changed in version 1.3.3.

minimalP(method=None)

Tests if the DFA is minimal

Parameters:

method (str) – minimization algorithm (here void)

Return type:

bool

Changed in version 1.3.3.

possibleToReverse()

Tests if language is reversible

New in version 1.3.3.

statePairEquiv(s1, s2)

Tests if two states of a ADFA are equivalent

Parameters:

• s1 (int) – state1

• s2 (int) – state2

Return type:

bool

New in version 1.3.3.

toANFA()

Converts the ADFA in a equivalent ANFA

Return type:

ANFA

toNFA()

Converts the ADFA in a equivalent NFA

Return type:

ANFA

New in version 1.2.

trim()

Remove states that do not lead to a final state, or, inclusively, that can’t be reached from the initial state. Only useful states remain.

Attention

in place transformation

wordGenerator()

Creates a random word generator

Returns:

the random word generator

Return type:

RndWGen

New in version 1.2.

class AFA

Base class for Acyclic Finite Automata

note: This is just a container for some common methods. Not to be used directly!!

abstract addState(_)

Return type:

int

directRank()

Compute rank function

Returns:

rank map

Return type:

dict

ensureDead()

Ensures that a state is defined as dead

evalRank()

Evaluates the rank map of a automaton

Returns:

pair of sets of states by rank map, reverse delta accessability map

Return type:

tuple

getLeaves()

The set of leaves, i.e. final states for last symbols of language words

Returns:

A set of leaves

Return type:

set

ordered()

Orders states names in its topological order

Returns:

ordered list of state indexes

Return type:

list of int

Note

one could use the FA.toposort() method, but special care must be taken with the dead state for the algorithms related with cover automata.

setDeadState(sti)

Identifies the dead state

Parameters:

sti (string) – index of the dead state

Attention

nothing is done to ensure that the state given is legitimate

Note

without dead state identified, most of the methods for acyclic automata can not be applied

class ANFA

Acyclic Nondeterministic Finite Automata class

mergeInitial()

Merge initial states

Attention

object is modified in place

mergeLeaves()

Merge leaves

Attention

object is modified in place

mergeStates(s1, s2)

Merge state s2 into state s1

Parameters:

• s1 (int) – state index

• s2 (int) – state index

Note

no attempt is made to check if the merging preserves the language of teh automaton

Attention

the object is modified in place

moveFinal(st, stf)

Unsets a set as final transfering transition to another final :param int st: the state to be ‘moved’ :param int stf: the destination final state

Note

stf must be a ‘last’ final state, i.e., must have no out transitions to anywhere but to a possible dead state

Attention

the object is modified in place

class BitString(blksz, alphsize, bst=None)

Class to represent the bitstring of a block language

Variables:

• blocksize – the size of the block

• alphsize – the size of the alphabet

• bst – the bitstring representation of the language

reverse()

Compute the BitString representation of the reverse of the current language.

class BlockWords(k: int, b: int)

Block language iterator

DFAtoADFA(aut)

Transforms an acyclic DFA into a ADFA

Parameters:

aut (DFA) – the automaton to be transformed

Returns:

the converted automaton

Return type:

ADFA

Raises:

notAcyclic – if the DFA is not acyclic

class DFCA

Deterministic Cover Automata class

property length

The length of the longest word :returns: the length of the longest word :rtype: int

class FL(wordsList=None, Sigma=None)

Finite Language Class

Variables:

• Words – the elements of the language

• Sigma – the alphabet

MADFA()

Generates the minimal acyclical DFA using specialized algorithm

New in version 1.3.3.

See also

Incremental Construction of Minimal Acyclic Finite-State Automata, J.Daciuk, blksz.Mihov, B.Watson and r.E.Watson

Return type:

ADFA

addWord(word)

Adds a word to a FL

Parameters:

word (string) – word to be added

Return type:

FL

addWords(wList)

Adds a list of words to a FL

Parameters:

wList (list) – words to be added

diff(other)

Difference of FL: a - b

Parameters:

other (FL) – left hand operand

Returns:

result of the operation

Return type:

FL

Raises:

FAdoGeneralError – if both arguments are not FL

filter(automata)

Separates a language in two other using a DFA of NFA as a filter

Parameters:

automata (dict) – the automata to be used as a filter

Returns:

the accepted/unaccepted pair of languages

Return type:

tuple of FL

intersection(other)

Intersection of FL: a & b

Parameters:

other (FL) – left hand operand

Returns:

result of the operation

Return type:

FL

Raises:

FAdoGeneralError – if both arguments are not FL

multiLineAutomaton()

Generates the trivial linear ANFA equivalent to this language

Returns:

the trivial linear ANFA

Return type:

ANFA

setSigma(Sigma, Strict=False)

Sets the alphabet of a FL

Parameters:

• Sigma (string) – alphabet

• Strict (bool) – behaviour

Attention

Unless Strict flag is set to True, alphabet can only be enlarged. The resulting alphabet is in fact the union of the former alphabet with the new one. If flag is set to True, the alphabet is simply replaced.

suffixClosedP()

Tests if a language is suffix closed

Returns:

True if language is suffix closed

Return type:

bool

toDFA()

Generates a DFA recognizing the language

Returns:

the DFA

Return type:

ADFA

New in version 1.2.

toNFA()

Generates a NFA recognizing the language

Return type:

ANFA

New in version 1.2.

trieFA()

Generates the trie automaton that recognises this language

Returns:

the trie automaton

Return type:

ADFA

union(other)

union of FL: a | b

Parameters:

other (FL) – right hand operand

Returns:

result of the union

Return type:

FL

Raises:

FAdoGeneralError – if both arguments are not FL

class RndWGen(aut)

Word random generator class

New in version 1.2.

Parameters:

aut (ADFA) – automata recognizing the language

blockUniversalP(a, n)

Parameters:

• a (NFA) – blksz NFA (= NFA accepting only words of same length)

• n (int) – length of accepted words

Returns:

whether a is blksz universal (accepts all words of length n)

Return type:

bool

coBlockDFA(a: DFA, n: int) → DFA

Parameters:

• a (DFA) – automaton accepting fixed length words

• n (int) – length of words accepted, n > 0

Returns:

accepts the words of length n not accepted by a

Return type:

DFA

New in version 2.1.2.

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

Generates the minimal ADFA that accepts exactly the first nwords (lexicographic order) of a blksz language

Parameters:

• alpzs (int) – alphabet size

• nwords (int) – number of words

• blksz (int) – blksz size

Returns:

the ADFA that recognises exacly those words

Return type:

ADFA

genRandomTrie(maxL, Sigma, safe=True)

Generates a random trie automaton for a finite language with a given length for max word

Parameters:

• maxL (int) – length of the max word

• Sigma (set) – alphabet to be used

• safe (bool) – should a word of size maxl be present in every language?

Returns:

the generated trie automaton

Return type:

ADFA

genRndBitString(b: int, k: int) → BitString

Generates a random bitstring with alphabet size k and block size b

Parameters:

• b (int) – The size of the block

• k (int) – The size of the alphabet

Returns:

the random bitstring

Return type:

bitarray

genRndTrieBalanced(maxL, Sigma, safe=True)

Generates a random trie automaton for a binary language of balanced words of a given leght for max word

Parameters:

• maxL (int) – the length of the max word

• Sigma (set) – the alphabet to be used

• safe (bool) – should a word of size maxl be present in every language?

Returns:

the generated trie automaton

Return type:

ADFA

genRndTriePrefix(maxL, Sigma, ClosedP=False, safe=True)

Generates a random trie automaton for a finite (either prefix free or prefix closed) language with a given length for max word

Parameters:

• maxL (int) – length of the max word

• Sigma (set) – alphabet to be used

• ClosedP (bool) – should it be a prefix closed language?

• safe (bool) – should a word of size maxl be present in every language?

Returns:

the generated trie automaton

Return type:

ADFA

genRndTrieUnbalanced(maxL, Sigma, ratio, safe=True)

Generates a random trie automaton for a binary language of balanced words of a given length for max word

Parameters:

• maxL (int) – length of the max word

• Sigma (set) – alphabet to be used

• ratio (int) – the ratio of the unbalance

• safe (bool) – should a word of size maxl be present in every language?

Returns:

the generated trie automaton

Return type:

ADFA

generateBlockTrie(sz: int, alpsz: int) → ADFA

Generates a trie for a blksz language

Parameters:

• sz (int) – size of the blksz

• alpsz (int) – size of the alphabet

Returns:

the automaton

Return type:

ADFA

New in version 2.1.3.

sigmaInitialSegment(Sigma: list, l: int, exact=False) → ADFA

Generates the ADFA recognizing Sigma^i for i<=l

Parameters:

• Sigma (list) – the alphabet

• l (int) – length

• exact (bool) – only the words with exactly that length?

Returns:

the automaton

Return type:

ADFA

stringToADFA(s)

Convert a canonical string representation of a ADFA to a ADFA

Parameters:

s (str) – the string in its canonical order

Returns:

the ADFA

Return type:

ADFA

See also

Marco Almeida, Nelma Moreira, and Rogério Reis. Exact generation of minimal acyclic deterministic finite automata. International Journal of Foundations of Computer Science, 19(4):751-765, August 2008.