FAdo.fa

Finite automata manipulation.

Deterministic and non-deterministic automata manipulation, conversion and evaluation.

class DFA

Class for Deterministic Finite Automata.

Variables:

• States (list) – set of states.

• sigma (set) – alphabet set.

• Initial (int) – the initial state index.

• Final (set) – set of final states indexes.

• delta (dict) – the transition function.

• delta_inv (dict) – possible inverse transition map

• i (bool) – is inverse map computed?

Delta(state, symbol)

Evaluates the action of a symbol over a state

Parameters:

• state (int) – state index

• symbol (Any) – symbol

Returns:

the action of symbol over state

Return type:

int

HKeqP(other, strict=True)

Tests the DFA’s equivalence using Hopcroft and Karp’s state equivalence algorithm

Parameters:

• other –

• strict –

Returns:

bool

See also

J. E. Hopcroft and r. M. Karp.A Linear Algorithm for Testing Equivalence of Finite Automata.TR 71–114. U. California. 1971

Attention

The automaton must be complete.

MyhillNerodePartition()

Myhill-Nerode partition, Moore’s way

New in version 1.3.5.

Attention

No state should be named with DeadName. This states is removed from the obtained partition.

See also

F.Bassino, J.David and C.Nicaud, On the Average Complexity of Moores’s State Minimization Algorihm, Symposium on Theoretical Aspects of Computer Science

aEquiv()

Computes almost equivalence, used by hyperMinimial

Returns:

partition of states

Return type:

dict

Note

may be optimized to avoid dupped

addTransition(sti1, sym, sti2)

Adds a new transition from sti1 to sti2 consuming symbol sym.

Parameters:

• sti1 (int) – state index of departure

• sti2 (int) – state index of arrival

• sym (Any) – symbol consumed

Raises:

DFAnotNFA – if one tries to add a non-deterministic transition

addTransitionIfNeeded(sti1: int, sym, sti2: int) → int

Adds a new transition from sti1 to sti2 consuming symbol sym, creating states if needed

Parameters:

• sti1 (int) – state index of departure

• sti2 (int) – state index of arrival

• sym (Any) – symbol consumed

Returns:

the destination state

Return type:

int

Raises:

DFAnotNFA – if one tries to add a non-deterministic transition

compat(s1, s2, data)

Tests compatibility between two states.

Parameters:

• data –

• s1 (int) – state index

• s2 (int) – state index

Return type:

bool

complete(dead='DeaD')

Transforms the automata into a complete one. If sigma is empty nothing is done.

Parameters:

dead (str) – dead state name

Returns:

the complete FA

Return type:

DFA

Note

Adds a dead state (if necessary) so that any word can be processed with the automata. The new state is named dead, so this name should never be used for other purposes.

Attention

The object is modified in place.

Changed in version 1.0.

completeMinimal()

Completes a DFA assuming it is a minimal and avoiding de destruction of its minimality If the automaton is not complete, all the non-final states are checked to see if tey are not already a dead state. Only in the negative case a new (dead) state is added to the automaton.

Return type:

DFA

Attention

The object is modified in place. If the alphabet is empty nothing is done

completeP()

Checks if it is a complete FA (if delta is total)

Returns:

bool

completeProduct(other)

Product structure

Parameters:

other (DFA) – the other DFA

Return type:

DFA

computeKernel()

The Kernel of a ICDFA is the set of states that accept a non-finite language.

Returns:

triple (comp, center , mark) where comp are the strongly connected components, center the set of center states and mark the kernel states

Return type:

tuple

concat(fa2, strict=False)

Concatenation of two DFAs. If DFAs are not complete, they are completed.

Parameters:

• strict (bool) – should alphabets be checked?

• fa2 (DFA) – the second DFA

Returns:

the result of the concatenation

Return type:

DFA

Raises:

DFAdifferentSigma – if alphabet are not equal

concatI(fa2, strict=False)

Concatenation of two DFAs.

Parameters:

• fa2 (DFA) – the second DFA

• strict (bool) – should alphabets be checked?

Returns:

the result of the concatenation

Return type:

DFA

Raises:

DFAdifferentSigma – if alphabet are not equal

New in version 0.9.5.

Note

this is to be used with non-complete DFAs

delTransition(sti1, sym, sti2, _no_check=False)

Remove a transition if existing and perform cleanup on the transition function’s internal data structure.

Parameters:

• sti1 (int) – state index of departure

• sym (Any) – symbol consumed

• sti2 (int) – state index of arrival

• _no_check (bool) – use unsecure code?

Note

Unused alphabet symbols will be discarded from sigma.

deleteStates(del_states)

Delete given iterable collection of states from the automaton.

Parameters:

del_states – collection of state indexes

Note

in-place action

Note

delta function will always be rebuilt, regardless of whether the states list to remove is a suffix, or a sublist, of the automaton’s states list.

static deterministicP()

Yes it is deterministic!

Return type:

bool

dist()

Evaluate the distinguishability language for a DFA

Return type:

DFA

See also

Cezar Câmpeanu, Nelma Moreira, Rogério Reis: The distinguishability operation on regular languages. NCMA 2014: 85-100

New in version 0.9.8.

distMin()

Evaluates the list of minimal words that distinguish each pair of states

Return type:

set of minimal distinguishing words (FL)

New in version 0.9.8.

Attention

If the DFA is not minimal, the method loops forever

distR()

Evaluate the right distinguishability language for a DFA

Return type:

DFA

..seealso:: Cezar Câmpeanu, Nelma Moreira, Rogério Reis:

The distinguishability operation on regular languages. NCMA 2014: 85-100

distRMin()

Compute distRMin for DFA

Return type:

FL

..seealso:: Cezar Câmpeanu, Nelma Moreira, Rogério Reis:

The distinguishability operation on regular languages. NCMA 2014: 85-100

distTS()

Evaluate the two-sided distinguishability language for a DFA

Return type:

DFA

..seealso:: Cezar Câmpeanu, Nelma Moreira, Rogério Reis:

The distinguishability operation on regular languages. NCMA 2014: 85-100

dup()

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

Return type:

DFA

enumDFA(n=None)

returns the set of words of words of length up to n accepted by self :param int n: highest length or all words if finite

Return type:

list of strings or None

equal(other)

Verify if the two automata are equivalent. Both are verified to be minimum and complete, and then one is matched against the other… Doesn’t destroy either dfa…

Parameters:

other (DFA) – the other DFA

Return type:

bool

evalSymbol(init, sym)

Returns the state reached from given state through a given symbol.

Parameters:

• init (int) – set of current states indexes

• sym (str) – symbol to be consumed

Returns:

reached state

Return type:

int

Raises:

• DFAsymbolUnknown – if symbol not in alphabet

• DFAstopped – if transition function is not defined for the given input

evalSymbolI(init, sym)

Returns the state reached from a given state.

Parameters:

• init (init) – current state

• sym (str) – symbol to be consumed

Returns:

reached state or -1

Return type:

set of int

Raises:

DFAsymbolUnknown – if symbol not in alphabet

New in version 0.9.5.

Note

this is to be used with non-complete DFAs

evalSymbolL(ls, sym)

Returns the set of states reached from a given set of states through a given symbol

Parameters:

• ls (set of int) – set of states indexes

• sym (str) – symbol to be read

Returns:

set of reached states

Return type:

set of int

evalSymbolLI(ls, sym)

Returns the set of states reached from a given set of states through a given symbol

Parameters:

• ls (set of int) – set of current states

• sym (str) – symbol to be consumed

Returns:

set of reached states

Return type:

set of int

New in version 0.9.5.

Note

this is to be used with non-complete DFAs

evalWord(wrd)

Evaluates a word

Parameters:

wrd (Word) – word

Returns:

final state or None

Return type:

int | None

New in version 1.3.3.

evalWordP(word, initial=None)

Verifies if the DFA recognises a given word

Parameters:

• word (list of symbols.) – word to be recognised

• initial (int) – starting state index

Return type:

bool

finalCompP(s)

Verifies if there is a final state in strongly connected component containing s.

Parameters:

s (int) – state

Returns:

1 if yes, 0 if no

hasTrapStateP()

Tests if the automaton has a dead trap state

Return type:

bool

New in version 1.1.

hxState(st: int) → str

A hash value for the transition of a state. The automaton needs to be complete.

Parameters:

st (int) – the state

Return type:

str

hyperMinimal(strict=False)

Hyperminization of a minimal DFA

Parameters:

strict (bool) – if strict=True it first minimizes the DFA

Returns:

an hyperminimal DFA

Return type:

DFA

See also

M. Holzer and A. Maletti, An nlogn Algorithm for Hyper-Minimizing a (Minimized) Deterministic Automata, TCS 411(38-39): 3404-3413 (2010)

Note

if strict=False minimality is assumed

inDegree(st)

Returns the in-degree of a given state in an FA

Parameters:

st (int) – index of the state

Return type:

int

infix()

Returns a dfa that recognizes infix(L(a))

Return type:

DFA

initialComp()

Evaluates the connected component starting at the initial state.

Returns:

list of state indexes in the component

Return type:

list of int

initialP(state)

Tests if a state is initial

Parameters:

state (int) – state index

Return type:

bool

initialSet()

The set of initial states

Returns:

the set of the initial states

Return type:

set

joinStates(lst)

Merge a list of states.

Parameters:

lst (iterable of state indexes.) – set of equivalent states

makeReversible()

Make a DFA reversible (if possible)

See also

M.Holzer, s. Jakobi, M. Kutrib ‘Minimal Reversible Deterministic Finite Automata’

Return type:

DFA

make_prefix_free()

Turns a DFA in a prefix-free automaton deleting all outgoing transitions from final states

Return type:

DFA

New in version 2.0.3.

markNonEquivalent(s1, s2, data)

Mark states with indexes s1 and s2 in given map as non-equivalent states. If any back-effects exist, apply them.

Parameters:

• s1 (int) – one state’s index

• s2 (int) – the other state’s index

• data – the matrix relating s1 and s2

mergeStates(f, t)

Merge the first given state into the second. If the first state is an initial state the second becomes the initial state.

Parameters:

• f (int) – index of state to be absorbed

• t (int) – index of remaining state

Attention

It is up to the caller to remove the disconnected state. This can be achieved with `trim().

minimal(method='minimalMooreSq', complete=True)

Evaluates the equivalent minimal complete DFA

Parameters:

• method – method to use in the minimization

• complete (bool) – should the result be completed?

Returns:

equivalent minimal DFA

Return type:

DFA

minimalHopcroft()

Evaluates the equivalent minimal complete DFA using Hopcroft algorithm

Returns:

equivalent minimal DFA

Return type:

DFA

See also

John Hopcroft,An n log{n} algorithm for minimizing states in a finite automaton.The Theory of Machines and Computations.AP. 1971

minimalHopcroftP()

Tests if a DFA is minimal

Return type:

bool

minimalIncremental(minimal_test=False, one_cicle=False)

Minimizes the DFA with an incremental method using the Union-Find algorithm and Memoized non-equivalence intermediate results

Parameters:

minimal_test (bool) – starts by verifying that the automaton is not minimal?

Returns:

equivalent minimal DFA

Return type:

DFA

See also

M. Almeida and N. Moreira and and r. Reis.Incremental DFA minimisation. CIAA 2010. LNCS 6482. pp 39-48. 2010

minimalIncrementalP()

Tests if a DFA is minimal

Return type:

bool

minimalMoore()

Evaluates the equivalent minimal automata with Moore’s algorithm

See also

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, AW, 1979

Returns:

minimal complete DFA

Return type:

DFA

minimalMooreSq()

Evaluates the equivalent minimal complete DFA using Moore’s (quadratic) algorithm

See also

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, AW, 1979

Returns:

equivalent minimal DFA

Return type:

DFA

minimalMooreSqP()

Tests if a DFA is minimal using the quadratic version of Moore’s algorithm

Return type:

bool

minimalNCompleteP()

Tests if a non necessarely complete DFA is minimal, i.e., if the DFA is non-complete, if the minimal complete has only one more state.

Returns:

True if not minimal

Return type:

bool

Attention

obsolete: use minimalP

minimalNotEquivP()

Tests if the DFA is minimal by computing the set of distinguishable (not equivalent) pairs of states

Return type:

bool

minimalP(method='minimalMooreSq')

Tests if the DFA is minimal

Parameters:

method – the minimization algorithm to be used

Return type:

bool

..note: if DFA non-complete test if complete minimal has one more state

minimalWatson(test_only=False)

Evaluates the equivalent minimal complete DFA using Waton’s incremental algorithm

Parameters:

test_only (bool) – is it only to test minimality

Returns:

equivalent minimal DFA

Return type:

DFA

Raises:

DFAnotComplete – if automaton is not complete

..attention::

automaton must be complete

minimalWatsonP()

Tests if a DFA is minimal using Watson’s incremental algorithm

Return type:

bool

notequal(other)

Test non equivalence of two DFAs

Parameters:

other (DFA) – the other DFA

Return type:

bool

orderedStrConnComponents()

Topological ordered list of strong components

New in version 1.3.3.

Return type:

list

pairGraph()

Returns pair graph

Return type:

DiGraphVM

See also

A graph theoretic apeoach to automata minimality. Antonio Restivo and Roberto Vaglica. Theoretical Computer Science, 429 (2012) 282-291. doi:10.1016/j.tcs.2011.12.049 Theoretical Computer Science, 2012 vol. 429 (C) pp. 282-291. http://dx.doi.org/10.1016/j.tcs.2011.12.049

possibleToReverse()

Tests if language is reversible

New in version 1.3.3.

pref()

Returns a dfa that recognizes pref(L(self))

Return type:

DFA

New in version 1.1.

prefix_free_p()

Checks is a DFA is prefix-free :rtype: bool

New in version 2.0.3.

print_data(data)

Prints table of compatibility (in the context of the minimalization algorithm).

Parameters:

data – data to print

product(other)

Returns a DFA resulting of the simultaneous execution of two DFA. No final states set.

Note

this is a fast version of the method. The resulting state names are not meaningfull.

Parameters:

other – the other DFA

Return type:

DFA

productSlow(other, complete=True)

Returns a DFA resulting of the simultaneous execution of two DFA. No final states set.

Note

this is a slow implementation for those that need meaningfull state names

New in version 1.3.3.

Parameters:

• other – the other DFA

• complete (bool) – evaluate product as a complete DFA

Return type:

DFA

reorder(dicti)

Reorders states according to given dictionary. Given a dictionary (not necessarily complete)… reorders states accordingly.

Parameters:

dicti (dict) – reorder dictionary

reverseTransitions(rev)

Evaluate reverse transition function.

Parameters:

rev (DFA) – DFA in which the reverse function will be stored

reversibleP()

Test if an automaton is reversible

Return type:

bool

sMonoid()

Evaluation of the syntactic monoid of a DFA

Returns:

the semigroup

Return type:

SSemiGroup

sSemigroup()

Evaluation of the syntactic semigroup of a DFA

Returns:

the semigroup

Return type:

SSemiGroup

shuffle(other, strict=False)

CShuffle of two languages: L1 W L2

Parameters:

• other (DFA) – second automaton

• strict (bool) – should the alphabets be necessary equal?

Return type:

DFA

See also

C. Câmpeanu, K. Salomaa and s. Yu, Tight lower bound for the state complexity of CShuffle of regular languages. J. Autom. Lang. Comb. 7 (2002) 303–310.

simDiff(other)

Symetrical difference

Parameters:

other –

Returns:

sop(other)

Strange operation

Parameters:

other (DFA) – the other automaton

Return type:

DFA

See also

Nelma Moreira, Giovanni Pighizzini, and Rogério Reis. Universal disjunctive concatenation and star. In Jeffrey Shallit and Alexander Okhotin, editors, Proceedings of the 17th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS15), number 9118 in LNCS, pages 197–208. Springer, 2015.

New in version 1.2b2.

star(flag=False)

Star of a DFA. If the DFA is not complete, it is completed.

..versionchanged: 0.9.6

Parameters:

flag (bool) – plus instead of star

Returns:

the result of the star

Return type:

DFA

starI()

Star of an incomplete DFA.

Returns:

the Kleene closure DFA

Return type:

DFA

stateChildren(state, strict=False)

Set of children of a state

Parameters:

• strict (bool) – if not strict a state is never its own child even if a self loop is in place

• state (int) – state id queried

Returns:

map children -> multiplicity

Return type:

dictionary

stronglyConnectedComponents()

Dummy method that uses the NFA conterpart

New in version 1.3.3.

Return type:

list

subword()

A dfa that recognizes subword(L(self))

Return type:

DFA

New in version 1.1.

succintTransitions()

Collects the transition information in a compact way suitable for graphical representation.

Returns:

list of tupples

Return type:

list

New in version 0.9.8.

suff()

Returns a dfa that recognizes suff(L(self))

Return type:

DFA

New in version 0.9.8.

syncPower()

Evaluates the Power automata for the action of each symbol

Returns:

The Power automata being the set of all states the initial state and all singleton states final

Return type:

DFA

toADFA()

Try to convert DFA to ADFA

Returns:

the same automaton as a ADFA

Return type:

ADFA

Raises:

notAcyclic – if this is not an acyclic DFA

New in version 1.2.

Changed in version 1.2.1.

toDFA()

Dummy function. It is already a DFA

Returns:

a self deep copy

Return type:

DFA

toNFA()

Migrates a DFA to a NFA as dup()

Returns:

DFA seen as new NFA

Return type:

NFA

transitions()

Iterator over transitions :rtype: symbol, int

transitionsA()

Iterator over transitions :rtype: symbol, int

uniqueRepr()

Normalise unique string for the string icdfa’s representation. .. seealso:: TCS 387(2):93-102, 2007 https://www.dcc.fc.up.pt/~nam/publica/tcsamr06.pdf

Returns:

normalised representation

Return type:

list

Raises:

DFAnotComplete – if DFA is not complete

universalP(minimal=False)

Checks if the automaton is universal through minimisation

Parameters:

minimal (bool) – is the automaton already minimal?

Return type:

bool

unmark()

Unmarked NFA that corresponds to a marked DFA: in which each alfabetic symbol is a tuple (symbol, index)

Returns:

a NFA

Return type:

NFA

usefulStates(initial_states=None)

Set of states reacheable from the given initial state(s) that have a path to a final state.

Parameters:

initial_states (iterable of int) – starting states

Returns:

set of state indexes

Return type:

set of int

witness()

Witness of non emptyness

Returns:

word

Return type:

str

witnessDiff(other)

Returns a witness for the difference of two DFAs and:

0	if the witness belongs to the other language
1	if the witness belongs to the self language

Parameters:

other (DFA) – the other DFA

Returns:

a witness word

Return type:

list of symbols

Raises:

DFAequivalent – if automata are equivalent

class EnumDFA(aut, store=False)

Class for enumerating languages defined by DFAs

fillStack(w)

Computes S_1,…,S_n-1 where S_i is the set of (n-i)-complete states reachable from S_i-1

Parameters:

w – word

initStack()

Initializes the stack with initial states

minWordT(n)

Computes for each state the minimal word of length i<n accepted by the automaton. Stores the values in tmin

Parameters:

n (int) – length of the word

Note

Makinen algorithm for DFAs

nextWord(w)

Given an word, returns next word on the nth cross-section of L(aut) according to the radix order

Parameters:

w (str) – word

Return type:

str

class EnumL(aut, store=False)

Class for enumerate FA languages

See: Efficient enumeration of words in regular languages, M. Ackerman and J. Shallit, Theor. Comput. Sci. 410, 37, pp 3461-3470. 2009. http://dx.doi.org/10.1016/j.tcs.2009.03.018

Variables:

• aut (FA) – Automaton of the language

• tmin (dict) – table for minimal words for each s in aut.States

• Words (list) – list of words (if stored)

• sigma (list) – alphabet

• stack (deque) –

New in version 0.9.8.

enum(m)

Enumerates the first m words of L(A) according to the lexicographic order if there are at least m words. Otherwise, enumerates all words accepted by A.

Parameters:

m (int) – max number of words

enumCrossSection(n)

Enumerates the nth cross-section of L(A)

Parameters:

n (int) – nonnegative integer

abstract fillStack(w)

Abstract method :param str w: :type w: str

iCompleteP(i, q)

Tests if state q is i-complete

Parameters:

• i (int) – int

• q (int) – state index

abstract initStack()

Abstract method

minWord(m)

Computes the minimal word of length m accepted by the automaton :param m: :type m: int

abstract minWordT(n)

Abstract method :param int n: :type n: int

abstract nextWord(w)

Abstract method :param w: :type w: str

class EnumNFA(aut, store=False)

Class for enumerating languages defined by NFAs

fillStack(w)

Computes S_1,…,S_n-1 where S_i is the set of (n-i)-complete states reachable from S_i-1

Parameters:

w – word

initStack()

Initializes the stack with initial states

minWordT(n)

Computes for each state the minimal word of length i <= n accepted by the automaton. Stores the values in tmin.

Parameters:

n (int) – length of the word

nextWord(w: str)

Given an word, returns next word in the the nth cross-section of L(aut) according to the radix order

Parameters:

w (str) – word

class FA

Base class for Finite Automata.

This is just an abstract class. Not to be used directly!!

Variables:

• States (list) – set of states.

• sigma (set) – alphabet set.

• Initial (int) – the initial state index.

• Final (set) – set of final states indexes.

• delta (dict) – the transition function.

addFinal(stateindex)

A new state is added to the already defined set of final states.

Parameters:

stateindex (int) – index of the new final state.

addSigma(sym)

Adds a new symbol to the alphabet.

Parameters:

sym (str) – symbol to be added

Raises:

DFAepsilonRedefinition – if sym is Epsilon

Note

• There is no problem with duplicate symbols because sigma is a Set.

• No symbol Epsilon can be added.

addState(name=None) → int

Adds a new state to an FA. If no name is given a new name is created.

Parameters:

name (Object, optional) – Name of the state to be added.

Returns:

Current number of states (the new state index).

Return type:

int

Raises:

DuplicateName – if a state with that name already exists

changeSigma(subst: dict)

Change the alphabet of an automaton by means of a sunstitution subst

Parameters:

subst (dict) – substitution

Raises:

FASiseMismatch – if substitution has a size different from existing alphabet

conjunction(other)

A simple literate invocation of __and__

Parameters:

other (FA) – right-hand operand.

Returns:

Intersection of self and other.

Return type:

FA

New in version 0.9.6.

countTransitions()

Evaluates the size of FA transitionwise

Returns:

the number of transitions

Return type:

int

Changed in version 1.0.

delFinal(st)

Deletes a state from the final states list

Parameters:

st (int) – state to be marked as not final.

delFinals()

Deletes all the information about final states.

disj(other)

Another simple literate invocation of __or__

Parameters:

other (FA) – the other FA.

Returns:

Union of self and other.

Return type:

FA

New in version 0.9.6.

disjunction(other)

A simple literate invocation of __or__

Parameters:

other (FA) – the other FA

Returns:

Union of self and other.

Return type:

FA

dotDrawState(sti: int, sep='\n', _strict=False, _maxlblsz=6)

Draw a state in dot format

Parameters:

• sti (int) – index of the state.

• sep (str, optional) – separator.

• _maxlblsz (int, optional) – max size of labels before getting removed

• _strict (bool, optional) – use limitations of label size

Returns:

string to be added to the dot file.

Return type:

str

static dotDrawTransition(st1, label, st2, sep='\n')

Draw a transition in dot format

Parameters:

• st1 (str) – departing state

• label (str) – label

• st2 (str) – arriving state

• sep (str) – separator

Return type:

str

dotFormat(size='20,20', filename=None, direction='LR', strict=False, maxlblsz=6, sep='\n') → str

A dot representation

Parameters:

• direction (str) – direction of drawing - “LR” or “RL”

• size (str) – size of image

• filename (str) – output file name

• sep (str) – line separator

• maxlblsz (int) – max size of labels before getting removed

• strict (bool) – use limitations of label sizes

Returns:

the dot representation

Return type:

str

New in version 0.9.6.

Changed in version 1.2.1.

eliminateDeadName()

Eliminates dead state name (common.DeadName) renaming the state

Returns:

self

Return type:

DFA

Attention

works inplace

New in version 1.2.

eliminateStout(st)

Eliminate all transitions outgoing from a given state

Parameters:

st (int) – the state index to lose all outgoing transitions

Attention

performs in place alteration of the automata

New in version 0.9.6.

equivalentP(other)

Test equivalence between automata

Parameters:

other (FA) – the other automata

Return type:

bool

New in version 0.9.6.

abstract evalSymbol(stil, sym)

Evaluation of a single symbol

finalP(state: int) → bool

Tests if a state is final

Parameters:

state (int) – state index.

Returns:

is the state final?

Return type:

bool

finalsP(states: set) → bool

Tests if al the states in a set are final

Parameters:

states (set) – set of state indexes.

Returns:

are all the states final?

Return type:

bool

New in version 1.0.

hasStateIndexP(st: int) → bool

Checks if a state index pertains to an FA

Parameters:

st (int) – index of the state.

Return type:

bool

images(sti: int, c)

The set of images of a state by a symbol

Parameters:

• sti (int) – state

• c (object) – symbol

Return type:

iterable

indexList(lstn)

Converts a list of stateNames into a set of stateIndexes.

Parameters:

lstn (list) – list of names

Returns:

the list of state indexes

Return type:

set

Raises:

DFAstateUnknown – if a state name is unknown

initialP(state: int) → bool

Tests if a state is initial

Parameters:

state – state index

Returns:

is the state initial?

Return type:

bool

initialSet()

The set of initial states

Returns:

set of States.

Return type:

set

inputS(i) → set[str]

Input labels coming out of state i

Parameters:

i (int) – state

Returns:

set of input labels

Return type:

set of str

New in version 1.0.

noBlankNames()

Eliminates blank names

Returns:

self

Return type:

FA

Attention

in place transformation

plus()

Plus of a FA (star without the adding of epsilon)

New in version 0.9.6.

renameState(st, name)

Rename a given state.

Parameters:

• st (int) – state index.

• name (object) – name.

Returns:

self.

Return type:

FA

Note

Deals gracefully both with int and str names in the case of name collision.

Attention

the object is modified in place

renameStates(name_list=None)

Renames all states using a new list of names.

Parameters:

name_list (list) – list of new names.

Returns:

self.

Return type:

FA

Raises:

DFAerror – if provided list is too short.

Note

If no list of names is given, state indexes are used.

Attention

the object is modified in place

reversal()

Returns a NFA that recognizes the reversal of the language

Returns:

NFA recognizing reversal language

Return type:

NFA

same_nullability(s1: int, s2: int) → bool

Tests if this two states have the same nullability

Parameters:

• s1 (int) – state index.

• s2 (int) – state index.

Returns:

have the states the same nullability?

Return type:

bool

setFinal(statelist)

Sets the final states of the FA

Parameters:

statelist (int|list|set) – a list (or set) of final states indexes.

Caution

Erases any previous definition of the final state set.

setInitial(stateindex)

Sets the initial state of a FA

Parameters:

stateindex (int) – index of the initial state.

setSigma(symbol_set)

Defines the alphabet for the FA.

Parameters:

symbol_set (list|set) – alphabet symbols

stateAlphabet(sti: int) → list

Active alphabet for this state

Parameters:

sti (int) – state

Return type:

list

stateIndex(name, auto_create=False)

Index of given state name.

Parameters:

• name (object) – name of the state.

• auto_create (bool, optional) – flag to create state if not already done.

Returns:

state index

Return type:

int

Raises:

DFAstateUnknown – if the state name is unknown and autoCreate==False

Note

Replaces stateName

Note

If the state name is not known and flag is set creates it on the fly

New in version 1.0.

stateName(name, auto_create=False)

Index of given state name.

Parameters:

• name (object) – name of the state

• auto_create (bool, optional) – flag to create state if not already done

Returns:

state index

Return type:

int

Raises:

DFAstateUnknown – if the state name is unknown and autoCreate==False

Deprecated since version 1.0: Use: stateIndex() instead

Deprecated since version 1.0: Use the stateIndex() method instead

abstract succintTransitions()

Collapsed transitions

union(other)

A simple literate invocation of __or__

Parameters:

other (FA) – right-hand operand.

Returns:

Union of self and other.

Return type:

FA

words(stringo=True)

Lexicographical word generator

Parameters:

stringo (bool, optional) – are words strings? Default is True.

Yields:

Word – the next word generated.

Attention

Does not generate the empty word

New in version 0.9.8.

class NFA

Class for Non-deterministic Finite Automata (epsilon-transitions allowed).

Variables:

• States (list) – set of states.

• sigma (set) – alphabet set.

• Initial (set) – initial state indexes.

• Final (set) – set of final states indexes.

• delta (dict) – the transition function.

HKeqP(other, strict=True)

Test NFA equivalence with extended Hopcroft-Karp method

Parameters:

• other (NFA) –

• strict (bool) – if True checks for same alphabets

Return type:

bool

See also

J. E. Hopcroft and r. M. Karp. A Linear Algorithm for Testing Equivalence of Finite Automata.TR 71–114. U. California. 1971

addEpsilonLoops()

Add epsilon loops to every state

Attention

in-place modification

New in version 1.0.

addInitial(stateindex)

Add a new state to the set of initial states.

Parameters:

stateindex (int) – index of new initial state

addTransition(sti1, sym, sti2)

Adds a new transition. Transition is from sti1 to sti2 consuming symbol sym. sti2 is a unique state, not a set of them.

Parameters:

• sti1 (int) – state index of departure

• sti2 (int) – state index of arrival

• sym (str) – symbol consumed

addTransitionQ(srci, dest, symb, qfuture, qpast)

Add transition to the new transducer instance.

Parameters:

• qpast (set) – past queue

• qfuture (set) – future queue

• symb – symbol

• dest (int) – destination state

• srci (int) – source state

New in version 1.0.

addTransitionStar(sti1, sti2, exception=())

Adds a new transition from sti1 to sti2 consuming any symbol

Parameters:

• sti1 (int) – state index of departure

• sti2 (int) – state index of arrival

• exception (list) – letters to excluded from the pattern

New in version 2.1.

autobisimulation()

Largest right invariant equivalence between states of the NFA

Returns:

Incomplete equivalence relation (transitivity, and reflexivity not calculated) as a set of unordered pairs of states

Return type:

set

See also

12. Ilie and S. Yu, Follow automata Inf. Comput. 186 - 1, pp 140-162, 2003

autobisimulation2() → list

Alternative space-efficient definition of NFA.autobisimulation.

Returns:

Incomplete equivalence relation (reflexivity, symmetry, and transitivity not calculated) as a set of pairs of states

Return type:

list

closeEpsilon(st)

Add all non epsilon transitions from the states in the epsilon closure of given state to given state.

Parameters:

st (int) – state index

Attention

in-place modification

computeFollowNames() → list

Computes the follow set to use in names

Return type:

list

concat(other, middle='middle')

Concatenation of NFA

Parameters:

• middle (str) – glue state name

• other (FA) – the other NFA

Returns:

the result of the concatenation

Return type:

NFA

countTransitions() → int

Count the number of transitions of a NFA

Return type:

int

delTransition(sti1, sym, sti2, _no_check=False)

Remove a transition if existing and perform cleanup on the transition function’s internal data structure.

Parameters:

• sti1 (int) – state index of departure

• sti2 (int) – state index of arrival

• sym – symbol consumed

• _no_check (bool) – dismiss secure code

Note

unused alphabet symbols will be discarded from sigma.

deleteStates(del_states)

Delete given iterable collection of states from the automaton.

Parameters:

del_states (set|list) – collection of int representing states

Note

delta function will always be rebuilt, regardless of whether the states list to remove is a suffix, or a sublist, of the automaton’s states list.

detSet(generic=False)

Computes the determination uppon a followFromPosition result

Return type:

NFA

deterministicP()

Verify whether this NFA is actually deterministic

Return type:

bool

dotFormat(size='20,20', filename=None, direction='LR', strict=False, maxlblsz=6, sep='\n') → str

A dot representation

Parameters:

• direction (str) – direction of drawing - “LR” or “RL”

• size (str) – size of image

• filename (str) – output file name

• sep (str) – line separator

• maxlblsz (int) – max size of labels before getting removed

• strict (bool) – use limitations of label sizes

Returns:

the dot representation

Return type:

str

New in version 0.9.6.

Changed in version 1.2.1.

dup()

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

Return type:

NFA

elimEpsilon()

Eliminate epsilon-transitions from this automaton.

:rtype : NFA

Attention

performs in place modification of automaton

Changed in version 1.1.1.

eliminateEpsilonTransitions()

Eliminates all epslilon-transitions with no state addition

Attention

in-place modification

eliminateTSymbol(symbol)

Delete all trasitions through a given symbol

Parameters:

symbol (str) – the symbol to be excluded from delta

Attention

in-place modification

New in version 0.9.6.

enumNFA(n=None)

The set of words of length up to n accepted by self

Parameters:

n (int) – highest lenght or all words if finite

Returns:

list of strings or None

Return type:

list

epsilonClosure(st)

Returns the set of states epsilon-connected to from given state or set of states.

Parameters:

st (int|set) – state index or set of state indexes

Returns:

the list of state indexes epsilon connected to st

Return type:

set

Attention

st must exist beforehand.

epsilonP()

Whether this NFA has epsilon-transitions

Return type:

bool

epsilonPaths(start: int, end: int) → set[int]

All states in all paths (DFS) through empty words from a given starting state to a given ending state.

Parameters:

• start (int) – start state

• end (int) – end state

Returns:

states in epsilon paths from start to end

Return type:

set

equivReduced(equiv_classes: UnionFind)

Equivalent NFA reduced according to given equivalence classes.

Parameters:

equiv_classes (UnionFind) – Equivalence classes

Returns:

Equivalent NFA

Return type:

NFA

evalSymbol(stil, sym)

Set of states reacheable from given states through given symbol and epsilon closure.

Parameters:

• stil (set|list) – set of current states

• sym (str) – symbol to be consumed

Returns:

set of reached state indexes

Return type:

set

Raises:

DFAsymbolUnknown – if symbol is not in alphabet

evalWordP(word)

Verify if the NFA recognises given word.

Parameters:

word (str) – word to be recognised

Return type:

bool

finalCompP(s)

Verify whether there is a final state in strongly connected component containing given state.

Parameters:

s (int) – state index

Return type:

bool

followFromPosition()

computes follow automaton from a Position automaton

Return type:

NFA

half()

Half operation

Return type:

NFA

New in version 0.9.6.

hasTransitionP(state, symbol=None, target=None)

Whether there’s a transition from given state, optionally through given symbol, and optionally to a specific target.

Parameters:

• state (int) – source state

• symbol (str) – (optional) transition symbol

• target (int) – (optional) target state

Returns:

if there is a transition

Return type:

bool

homogeneousFinalityP() → bool

Tests if states have incoming transitions froms states with different finalities

Return type:

bool

homogenousP(x)

Whether this NFA is homogenous; that is, for all states, whether all incoming transitions to that state are through the same symbol.

Parameters:

x – dummy parameter to agree with the method in DFAr

Return type:

bool

initialComp()

Evaluate the connected component starting at the initial state.

Returns:

list of state indexes in the component

Return type:

list of int

lEquivNFA()

Equivalent NFA obtained from merging equivalent states from autobisimulation of this NFA’s reversal.

Return type:

NFA

Note

returns copy of self if autobisimulation renders no equivalent states.

lrEquivNFA()

Equivalent NFA obtained from merging equivalent states from autobisimulation of this NFA, and from autobisimulation of its reversal; i.e., merges all states that are equivalent w.r.t. the largest right invariant and largest left invariant equivalence relations.

Return type:

NFA

Note

returns copy of self if autobisimulations render no equivalent states.

minimal()

Evaluates the equivalent minimal DFA

Returns:

equivalent minimal DFA

Return type:

DFA

minimalDFA()

Evaluates the equivalent minimal complete DFA

Returns:

equivalent minimal DFA

Return type:

DFA

product(other)

Returns a NFA (skeletom) resulting of the simultaneous execution of two DFA.

Parameters:

other (NFA) – the other automata

Return type:

NFA

Raises:

NFAerror – if any argument has epsilon-transitions

Note

No final states are set.

Attention

• operands cannot have epsilon-transitions

• the name EmptySet is used in a unique special state name

• the method uses 3 internal functions for simplicity of code (really!)

rEquivNFA()

Equivalent NFA obtained from merging equivalent states from autobisimulation of this NFA.

Return type:

NFA

Note

returns copy of self if autobisimulation renders no equivalent states.

renameStatesFromPosition()

Rename states of a Glushkov automaton using the positions of the marked RE

Return type:

NFA

reorder(dicti)

Reorder states indexes according to given dictionary.

Parameters:

dicti (dict) – state name reorder

Attention

in-place modification

Note

dictionary does not have to be complete

reversal()

Returns a NFA that recognizes the reversal of the language

Returns:

NFA recognizing reversal language

Return type:

NFA

reverseTransitions(rev)

Evaluate reverse transition function.

Parameters:

rev (NFA) – NFA in which the reverse function will be stored

setInitial(statelist)

Sets the initial states of an NFA

Parameters:

statelist (set|list|int) – an iterable of initial state indexes

shuffle(other)

Shuffle of a NFA

Parameters:

other (FA) – an FA

Returns:

the resulting NFA

Return type:

NFA

star(flag=False)

Kleene star of a NFA

Parameters:

flag (bool) – plus instead of star?

Returns:

the resulting NFA

Return type:

NFA

stateChildren(state: int, strict=False) → set[int]

Set of children of a state

Parameters:

• state (int) – state id queried

• strict (bool) – if not strict a state is never its own child even if a self loop is in place

Returns:

children states

Return type:

set

stronglyConnectedComponents()

Strong components

Return type:

list

New in version 1.0.

subword()

NFA that recognizes subword(L(self))

Return type:

NFA

succintTransitions()

Collects the transition information in a compact way suitable for graphical representation. :rtype: list

toDFA()

Construct a DFA equivalent to this NFA, by the subset construction method.

Return type:

DFA

Note

valid to epsilon-NFA

toNFA()

Dummy identity function

Return type:

NFA

toNFAr()

NFA with the reverse mapping of the delta function.

Returns:

shallow copy with reverse delta function added

Return type:

NFAr

uniqueRepr() → tuple

Dummy representation. Used DFA.uniqueRepr()

Return type:

tuple

universalP()

Whether this NFA is universal (accetps all words)

usefulStates(initial_states=None)

Set of states reacheable from the given initial state(s) that have a path to a final state.

Parameters:

initial_states (set) – set of initial states

Returns:

set of state indexes

Return type:

set

witness()

Witness of non emptiness

Returns:

word

Return type:

str

wordImage(word, ist=None)

Evaluates the set of states reached consuming given word

Parameters:

• word – the word

• ist (int) – starting state index (or set of)

Returns:

the set of ending states

Return type:

set of int

class NFAr

Class for Non-deterministic Finite Automata with reverse delta function added by construction.

Includes efficient methods for merging states.

addTransition(sti1, sym, sti2)

Adds a new transition. Transition is from sti1 to sti2 consuming symbol sym. sti2 is a unique state, not a set of them. Reversed transition function is also computed

Parameters:

• sti1 (int) – state index of departure

• sti2 (int) – state index of arrival

• sym (str) – symbol consumed

delTransition(sti1, sym, sti2, _no_check=False)

Remove a transition if existing and perform cleanup on the transition function’s internal data structure and in the reversal transition function

Parameters:

• sti1 (int) – state index of departure

• sti2 (int) – state index of arrival

• sym (str) – symbol consumed

• _no_check (bool) – (optional) dismiss secure code

deleteStates(del_states)

Delete given iterable collection of states from the automaton. Performe deletion in the transition function and its reversal.

Parameters:

del_states (set|list) – collection of states indexes

elimEpsilonO()

Eliminate epsilon-transitions from this automaton, with reduction of states through elimination of Epsilon-cycles, and single epsilon-transition cases.

Return type:

NFAr

Attention

performs inplace modification of automaton

homogenousP(inplace=False)

Checks is the automaton is homogenous, i.e.the transitions that reaches a state have all the same label.

Parameters:

inplace (bool) – if True performs Epsilon transitions elimination

Returns:

True if homogenous

Return type:

bool

mergeStates(f, t)

Merge the first given state into the second. If first state is an initial or final state, the second becomes respectively an initial or final state.

Parameters:

• f (int) – index of state to be absorbed

• t (int) – index of remaining state

Attention

It is up to the caller to remove the disconnected state. This can be achieved with `trim().

mergeStatesSet(tomerge, target=None)

Merge a set of states with a target merge state. If the states in the set have transitions among them, those transitions will be directly merged into the target state.

Parameters:

• tomerge (set) – set of states to merge with target

• target (int) – optional target state

Note

if target state is not given, the minimal index with be considered.

Attention

The states of the list will become unreacheable, but won’t be removed. It is up to the caller to remove them. That can be achieved with trim().

toNFA()

Turn into an instance of NFA, and remove the reverse mapping of the delta function.

Returns:

shallow copy without reverse delta function

Return type:

NFA

unlinkSoleIncoming(state)

If given state has only one incoming transition (indegree is one), and it’s through epsilon, then remove such transition and return the source state.

Parameters:

state (int) – state to check

Returns:

source state

Return type:

int | None

Note

if conditions aren’t met, returned source state is None, and automaton remains unmodified.

unlinkSoleOutgoing(state)

If given state has only one outgoing transition (outdegree is one), and it’s through epsilon, then remove such transition and return the target state.

Parameters:

state (int) – state to check

Returns:

target state

Return type:

int | None

Note

if conditions aren’t met, returned target state is None, and automaton remains unmodified.

class OFA

Base class for one-way automata

Variables:

• States (list) – set of states.

• sigma (set) – alphabet set.

• Initial (int) – the initial state index.

• Final (set) – set of final states indexes.

• delta (dict) – the transition function.

acyclicP(strict=True)

Checks if the FA is acyclic

Parameters:

strict (bool) – if not True loops are allowed

Returns: True if the FA is acyclic

bool: True if the FA is acyclic

abstract addTransition(st1, sym, st2)

Add transition

Parameters:

• st1 (int) – departing state

• sym (str) – label

• st2 (int) – arriving state

dotDrawTransition(st1, label, st2, sep='\n')

Draw a transition in dot format

Parameters:

• st1 (str) – departing state

• label (str) – symbol

• st2 (str) – arriving state

• sep (str) – separator

Return type:

str

dump()

Returns a python representation of the object

Returns:

the python representation (Tags,States,sigma,delta,Initial,Final)

Return type:

tuple

emptyP()

Tests if the automaton accepts an empty language

Return type:

bool

New in version 1.0.

abstract evalSymbol(stil, sym)

Eval symbol

leftQuotient(other)

Returns the quotient (NFA) of a language by another language, both given by FA.

Parameters:

other (OFA) – the language to be quotient by

Returns:

the quotient

Return type:

NFA

minimalBrzozowski()

Constructs the equivalent minimal DFA using Brzozowski’s algorithm

Returns:

equivalent minimal DFA

Return type:

DFA

minimalBrzozowskiP()

Tests if the FA is minimal using Brzozowski’s algorithm

Return type:

bool

quotient(other)

Synonymous of leftQotient

rightQuotient(other)

Returns the quotient (NFA) of a language by another language, both given by FA.

Parameters:

other (OFA) – the language to be quotient by

Returns:

the quotient

Return type:

NFA

abstract stateChildren(_state, _strict=None)

To be implemented below

Parameters:

• _state (state) –

• _strict (int) – state id queried

Return type:

list

abstract succintTransitions()

Collapsed transitions

topoSort()

Topological order for the FA

Returns:

List of state indexes

Return type:

list

Note

self loops are taken in consideration

trim()

Removes the states that do not lead to a final state, or, inclusively,

that can’t be reached from the initial state. Only useful states remain.

Return type:

FA

Attention

in place transformation

trimP()

Tests if the FA is trim: initially connected and co-accessible

Return type:

bool

class SemiDFA

Class of automata without initial or final states

Variables:

• States (list) – set of states.

• sigma (set) – alphabet set.

• delta (dict) – the transition function.

dotDrawState(sti: int, sep='\n') → str

Dot representation of a state

Parameters:

• sti (int) – state index.

• sep (str, optional) – separator.

Returns:

line to add to the dot file.

Return type:

str

static dotDrawTransition(st1: str, lbl1: str, st2, sep='\n') → str

Draw a transition in dot format

Parameters:

• st1 (str) – departing state.

• lbl1 (str) – label.

• st2 (str) – arriving state.

• sep (str, optional) – separator.

Returns:

line to add to the dot file.

Return type:

str

dotFormat(size='20,20', filename=None, direction='LR', strict=False, maxlblsz=6, sep='\n') → str

A dot representation

Parameters:

• direction (str) – direction of drawdrawing - “LR” or “RL”

• size (str) – size of image

• filename (str) – Name of the output file

• sep (str) – line separator

• maxlblsz (int) – max size of labels before getting removed

• strict (bool) – use limitations of label sizes

Returns:

the dot representation

Return type:

str

New in version 0.9.6.

Changed in version 1.2.1.

emptyDFA(sigma=None)

Given an alphabet returns the minimal DFA for the empty language

Parameters:

sigma (set) – set of symbols

Return type:

DFA

New in version 1.3.4.2.

reduce_size(aut: DFA, maxIter=None) → DFA

A smaller (if possible) DFA. To use with huge automata.

Parameters:

• aut (DFA) – the aoutomata to reduce

• maxIter (int) – the maxiimum number of iterations before return

Return type:

DFA

saveToString(aut: FA, sep='&') → str

Finite automata definition as a string using the input format.

New in version 0.9.5.

Changed in version 0.9.6: Names are now used instead of indexes.

Changed in version 0.9.7: New format with quotes and alphabet

Parameters:

• aut (FA) – the FA

• sep (str) – separation between lines

Returns:

the representation

Return type:

str

sigmaStarDFA(sigma=None) → DFA

Given a alphabet s returns the minimal DFA for s*

Parameters:

sigma (set) – set of simbols

Return type:

DFA

New in version 1.2.

statePP(state)

Pretty print state

Parameters:

state –

Returns:

stringToDFA(s: list, f: list, n: int, k: int) → DFA

Converts a string icdfa’s representation to dfa.

Parameters:

• s (list) – canonical string representation

• f (list) – bit map of final states

• n (int) – number of states

• k (int) – number of symbols

Returns:

a complete dfa with sigma [k], States [n]

Return type:

DFA

Changed in version 0.9.8: symbols are converted to str

symbolDFA(sym, sigma=None) → DFA

Given symbol and an alphabet returns the minimal DFA that aceepts that symbol

Parameters:

• sym – symbol

• sigma (set) – set of symbols

Return type:

DFA